A Combinatorial Problem Which Is Complete in Polynomial Space

DOI10.1145/321978.321989zbMath0355.68041OpenAlexW1965172764WikidataQ56212888 ScholiaQ56212888MaRDI QIDQ4127387

Shimon Even, Robert Endre Tarjan

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321978.321989

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99) Word problems, etc. in computability and recursion theory (03D40) Algorithms in computer science (68W99)

Related Items

PSPACE-Hardness of some combinatorial games, On the complexity of connection games, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Complexity of question/answer games, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, Topological games at Princeton, a mathematical memoir, UNO is hard, even for a single player, Havannah and TwixT are PSPACE-complete, Phutball is PSPACE-hard, A note on first-order projections and games., The complexity of problems in systems of communicating sequential processes, On the complexity of computational problems associated with simple stochastic games, Hex and combinatorics, Playing disjunctive sums is polynomial space complete, Unnamed Item, Theory of annihilation games. I, Some Completeness Results on Decision Trees and Group Testing, A difficulty in particular Shannon-like games, The complexity of recursion theoretic games, Hanabi is NP-hard, even for cheaters who look at their cards, Complexity of path-forming games, Lower bounds for multiplayer noncooperative games of incomplete information, The set coincidence game: Complexity, attainability, and symmetric strategies, Game edge-connectivity of graphs, A hierarchical approach to computer Hex, Games solved: Now and in the future, On the complexity of some two-person perfect-information games, Theory of division games, The largest connected subgraph game, The largest connected subgraph game, Twenty years of progress of \(\mathrm{JCDCG}^3\), Complexity of path discovery game problems, Recent results and questions in combinatorial game complexities, Colored cut games, On the complexity of chess, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., The complexity of two-player games of incomplete information, On Ringeisen's isolation game. II, The Othello game on an \(n\times n\) board is PSPACE-complete, Decision algorithms for multiplayer noncooperative games of incomplete information