---
title: "Stefan Reisch"
type: "entity"
entity_kind: "person"
status: "hub"
canonical_name: "Stefan Reisch"
aliases: []
first_seen: "2026-08-21T00:00:00.000Z"
writer_model: "claude-sonnet-5"
connects_to: ["Hex (game)","PSPACE-completeness","computational complexity","John Nash","non-constructive proof"]
seek_code_commit: "17d9798"
---


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 [[entity-john-nash|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