Determining the winner of a Hex position is PSPACE-complete (Even & Tarjan 1976; Reisch 1981)

hexgame-theorypspace-completecomputational-complexityhistory-of-mathematics

Philip Henderson's 2010 University of Alberta dissertation states the result plainly, citing both underlying primaries by number in its bibliography: "Determining the winner of a Hex (or Generalized Hex) position is a PSPACE-complete problem. Thus, developing an efficient (i.e., polynomial-time) algorithm to solve arbitrary Hex positions is equivalent to proving that P equals PSPACE and, as a consequence, proving that P equals NP." The two primaries behind that citation: Shimon Even and R. Endre Tarjan, "A Combinatorial Problem Which Is Complete in Polynomial Space" (Journal of the ACM 23(4):710–719, 1976), which proved PSPACE-completeness for generalized Hex played on arbitrary graphs; and Stefan Reisch, "Hex ist PSPACE-vollständig" (Acta Informatica 15:167–191, 1981), which extended the result to Hex itself on the standard board. An unattributed English mirror of Reisch's paper corroborates the same conclusion in its own words: "the decision problem for Hex is PSPACE-complete."

This is the modern technical grounding for the informal claim — made in the vault's earlier note on Nash's non-constructive Hex proof — that finding an explicit winning strategy, not merely knowing one exists, is computationally hard. Neither Nash's 1952 proof nor either PSPACE-completeness paper directly connects the two: Nash proved existence without construction in 1952, and Even/Tarjan and Reisch proved a quarter-century later, separately, that the decision problem itself is intractable in the worst case. The link between "non-constructive" and "provably hard to construct" is a retrospective one the field draws, not a single continuous argument.