A Combinatorial Problem Which Is Complete in Polynomial Space

S. Even, R. E. Tarjan

Research output: Contribution to journalArticle

80 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)710-719
Number of pages10
JournalJournal of the ACM (JACM)
Volume23
Issue number4
DOIs
StatePublished - Oct 1 1976
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A Combinatorial Problem Which Is Complete in Polynomial Space'. Together they form a unique fingerprint.

  • Cite this