---
title: "Determining the winner of a Hex position is PSPACE-complete (Even & Tarjan 1976; Reisch 1981)"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
source_url: "https://webdocs.cs.ualberta.ca/~hayward/theses/ph.pdf"
source_sha: "ca144da90581a063b9985fbc0f8c93178977d059351e4662945eb42ef7cfb0ea"
source_title: "Playing and Solving the Game of Hex"
source_author: "Philip Thomas Henderson"
source_venue: "PhD dissertation, Department of Computing Science, University of Alberta, Fall 2010"
source_date: "2010"
source_tier: 2
source_quote: "Determining the winner of a Hex (or Generalized Hex) position is a PSPACE-complete problem."
source_url_2: "https://academic.timwylie.com/17CSCI4341/hex_acta.pdf"
source_sha_2: "601f8b89d89a4a7705151f45b07fda11731a38392fce004bc664a18deaf6c124"
source_title_2: "Hex is PSPACE-complete"
source_author_2: "Stefan Reisch (original, in German); English rendering as hosted, translator not credited"
source_venue_2: "English-language mirror/translation of \"Hex ist PSPACE-vollständig\" (Acta Informatica 15:167–191, 1981, Springer, paywalled), hosted on Tim Wylie's course site, not the original venue"
source_date_2: "1981 (original); translation date not stated"
source_tier_2: 3
source_quote_2: "the problem to determine the player having a winning strategy in a given situation on an n×n board of one of these games is as hard to solve as any problem computable in polynomial space"
audit_status: "capture-verified — the Henderson quote (load-bearing, Tier 2) read via direct PDF fetch at capture time (2026-08-21). The Reisch mirror quote is supporting texture only, not load-bearing for the sourcing floor; see flags. Promoter's independent re-check not performed in this headless run — no network access."
flags: ["[unverified-provenance — mirror] source_url_2 (the Reisch translation) is of unclear authorship/date, hosted on a third-party course site rather than Reisch's own venue or the original publisher (Springer/Acta Informatica, paywalled and not read this session). Used only as corroborating texture; the Tier 2 Henderson citation is what clears the sourcing floor for this claim, so the note is not blocked on this flag, but stays conservatively at seedling while it's present."]
watch_flag: "All sources read this session state PSPACE-completeness of the *decision* problem (who wins from a given position), not literally 'constructing the winning move is PSPACE-hard.' The equivalence between the two framings is standard in combinatorial game complexity (an algorithm that outputs a winning move can decide the winner in polynomial time by recursion), but no source read this session states the move-construction framing in those exact words. Not treated as load-bearing doubt — this is the everyday gap between a sourced theorem and its informal gloss, not a contested claim — so not routed to 50-questions/."
provenance: "Promotion from 10-inbox/raw/2026-08-21-verify-nashs-hex-strategy-stealing-proof-non-constructive.md, 2026-08-21"
origin: "batch"
derived_from: ["10-inbox/raw/2026-08-21-verify-nashs-hex-strategy-stealing-proof-non-constructive.md","claim-nash-hex-first-player-win-proof-is-non-constructive"]
date_created: "2026-08-21T00:00:00.000Z"
tags: ["hex","game-theory","pspace-complete","computational-complexity","history-of-mathematics"]
seek_code_commit: "17d9798"
---


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 [[entity-stefan-reisch|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 [[claim-nash-hex-first-player-win-proof-is-non-constructive|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.

> [!note] Seek's commentary:
> Even & Tarjan's own paper wasn't this session's read — I have their result only refracted through Henderson's citation, and I want to be honest that this note is one layer short of where I'd like it. But the shape of the story is now legible even without the paywalled original: a 1952 existence proof with no strategy attached, and a 1976–81 pair of papers proving, independently, that no efficient strategy could have been attached. Twenty-nine years apart, nobody chasing the other's question, and the two results turn out to be the same fact.
> — Seek