A combinatorial problem which is complete in polynomial space

Shimon Even; R. Endre Tarjan

A combinatorial problem which is complete in polynomial space

Research output: Contribution to journal › Conference article › peer-review

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 language	English (US)
Pages (from-to)	66-71
Number of pages	6
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
State	Published - May 5 1975
Externally published	Yes
Event	7th Annual ACM Symposium on Theory of Computing, STOC 1975 - Albuquerque, United States Duration: May 5 1975 → May 7 1975

All Science Journal Classification (ASJC) codes

Software

Keywords

Completeness in polynomial space
Computational complexity
HEX
Shannon switching game

Cite this

@article{53ac264636c848f5a9e1c2427cd9f352,

title = "A combinatorial problem which is complete in polynomial space",

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

keywords = "Completeness in polynomial space, Computational complexity, HEX, Shannon switching game",

author = "Shimon Even and Tarjan, \{R. Endre\}",

note = "Publisher Copyright: {\textcopyright} 1975 Association for Computing Machinery. All rights reserved.; 7th Annual ACM Symposium on Theory of Computing, STOC 1975 ; Conference date: 05-05-1975 Through 07-05-1975",

year = "1975",

month = may,

day = "5",

language = "English (US)",

pages = "66--71",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

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

}

TY - JOUR

T1 - A combinatorial problem which is complete in polynomial space

AU - Even, Shimon

AU - Tarjan, R. Endre

PY - 1975/5/5

Y1 - 1975/5/5

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

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

KW - Completeness in polynomial space

KW - Computational complexity

KW - HEX

KW - Shannon switching game

UR - https://www.scopus.com/pages/publications/0039346371

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

M3 - Conference article

AN - SCOPUS:0039346371

SN - 0737-8017

SP - 66

EP - 71

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 7th Annual ACM Symposium on Theory of Computing, STOC 1975

Y2 - 5 May 1975 through 7 May 1975

ER -

A combinatorial problem which is complete in polynomial space

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this