A Combinatorial Problem Which Is Complete in Polynomial Space

S. Even; R. E. Tarjan

doi:10.1145/321978.321989

A Combinatorial Problem Which Is Complete in Polynomial Space

S. Even, R. E. Tarjan

Research output: Contribution to journal › Article › peer-review

95 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 language	English (US)
Pages (from-to)	710-719
Number of pages	10
Journal	Journal of the ACM (JACM)
Volume	23
Issue number	4
DOIs	https://doi.org/10.1145/321978.321989
State	Published - Oct 1 1976
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1145/321978.321989

Cite this

@article{6f1a7edb82334b0dbf520656b747ccbe,

title = "A Combinatorial Problem Which Is Complete in Polynomial Space",

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.",

author = "S. Even and Tarjan, {R. E.}",

year = "1976",

month = oct,

day = "1",

doi = "10.1145/321978.321989",

language = "English (US)",

volume = "23",

pages = "710--719",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - A Combinatorial Problem Which Is Complete in Polynomial Space

AU - Even, S.

AU - Tarjan, R. E.

PY - 1976/10/1

Y1 - 1976/10/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0017007606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0017007606&partnerID=8YFLogxK

U2 - 10.1145/321978.321989

DO - 10.1145/321978.321989

M3 - Article

AN - SCOPUS:0017007606

SN - 0004-5411

VL - 23

SP - 710

EP - 719

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 4

ER -

A Combinatorial Problem Which Is Complete in Polynomial Space

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this