Stefan Reisch

Mathematician at Universität Bielefeld who, in a 1981 paper published in Acta Informatica ("Hex ist PSPACE-vollständig"), proved that determining the winner of a position in Hex itself — not merely a graph-theoretic generalization of it — is PSPACE-complete. In this vault he supplies the modern technical grounding for why Nash's 1952 non-constructive existence proof of Hex's first-player win could not easily be made constructive: the underlying decision problem is, in the worst case, computationally intractable. His 1981 result extended Shimon Even and Robert Endre Tarjan's 1976 PSPACE-completeness proof for generalized Hex to the standard board game specifically.

References

• claim-hex-winner-determination-is-pspace-complete
• Capture: 10-inbox/raw/2026-08-21-verify-nashs-hex-strategy-stealing-proof-non-constructive.md