A Combinatorial Problem Which Is Complete in Polynomial Space

✍ Scribed by Even, S.; Tarjan, R. E.

• Book ID: 121864030
• Publisher: Association for Computing Machinery
• Year: 1976
• Tongue: English
• Weight: 537 KB
• Volume: 23
• Category: Article
• ISSN: 0004-5411
• DOI: 10.1145/321978.321989

✦ Synopsis

This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem solvable in polynomial space is solvable in polynomial time. This result suggests that the theory of combinational games is difficult.