A combinatorial problem which is complete in polynomial space

Shimon Even, R. Endre Tarjan

Research output: Contribution to journalConference article

14 Scopus citations

Abstract

We consider a generalization, which we call the Shannon switching game on vertices, of a familiar board game called HEX. We show that determining who wins such a game if each player plays perfectly is very hard; in fact, it is as hard as carrying out any polynomial-space-bounded computation. This result suggests that the theory of combinatorial games is difficult.

Original languageEnglish (US)
Pages (from-to)66-71
Number of pages6
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - May 5 1975
Externally publishedYes
Event7th Annual ACM Symposium on Theory of Computing, STOC 1975 - Albuquerque, United States
Duration: May 5 1975May 7 1975

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Completeness in polynomial space
  • Computational complexity
  • HEX
  • Shannon switching game

Fingerprint Dive into the research topics of 'A combinatorial problem which is complete in polynomial space'. Together they form a unique fingerprint.

  • Cite this