Editing Hex (board game) (section)

===Computational complexity===
In 1976, [[Shimon Even]] and [[Robert Tarjan]] proved that determining whether a position in a game of generalized Hex played on arbitrary graphs is a winning position is [[PSPACE-complete]].<ref>{{Cite journal|doi = 10.1145/321978.321989|title = A Combinatorial Problem Which is Complete in Polynomial Space|year = 1976|last1 = Even|first1 = S.|last2 = Tarjan|first2 = R. E.|journal = Journal of the ACM|volume = 23|issue = 4|pages = 710–719|s2cid = 8845949|doi-access = free}}</ref>
A strengthening of this result was proved by Reisch by reducing the [[True quantified Boolean formula|quantified Boolean formula problem]] in [[conjunctive normal form]] to Hex.<ref>{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Informatica | issue = 2 | year = 1981 | pages = 167–191 |  volume=15 | doi=10.1007/bf00288964| s2cid = 9125259 }}</ref> This result means that there is no efficient (polynomial time in board size) algorithm to solve an arbitrary Hex position unless there is an efficient algorithm for all PSPACE problems, which is widely believed not to be the case.<ref>Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach". Cambridge University Press, 2009. Section 4.3</ref> However, it doesn't rule out the possibility of a simple winning strategy for the initial position (on boards of arbitrary size), or a simple winning strategy for all positions on a board of a particular size.

In 11×11 Hex, the state space complexity is approximately 2.4×10<sup>56</sup>;<ref>{{cite book|last1=Browne|first1=C|title=Hex Strategy|date=2000|publisher=A.K. Peters, Ltd.|location=Natick, MA|isbn=1-56881-117-9|pages=5–6}}</ref> versus 4.6×10<sup>46</sup> for chess.<ref>{{cite web|last1=Tromp |first1=J |title=Number of chess diagrams and positions |url=http://homepages.cwi.nl/~tromp/chess/chess.html |website=John's Chess Playground |url-status=bot: unknown |archive-url=https://web.archive.org/web/20110629215923/http://homepages.cwi.nl/~tromp/chess/chess.html |archive-date=29 June 2011}}</ref> The game tree complexity is approximately 10<sup>98</sup><ref>H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. </ref> versus 10<sup>123</sup> for chess.<ref>Victor Allis (1994). ''Searching for Solutions in Games and Artificial Intelligence''. Ph.D. Thesis, University of Limburg, pdf, 6.3.9 Chess pp. 171</ref>