On the complexity of some two-person perfect-information games
From MaRDI portal
Publication:1248466
DOI10.1016/0022-0000(78)90045-4zbMath0383.90112OpenAlexW2042714866WikidataQ56850877 ScholiaQ56850877MaRDI QIDQ1248466
Publication date: 1978
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(78)90045-4
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Turing machines and related notions (03D10)
Related Items
The maker-maker domination game in forests, The general position avoidance game and hardness of general position games, On the complexity of computational problems associated with simple stochastic games, Bipartite instances of INFLUENCE, Feedback game on \(3\)-chromatic Eulerian triangulations of surfaces, Unnamed Item, Winner determination algorithms for graph games with matching structures, Connected Subtraction Games on Subdivided Stars, The game total domination problem is log-complete in PSPACE, On the computational complexities of various geography variants, Computational Hardness of Multidimensional Subtraction Games, Games, Puzzles and Treewidth, PSPACE-hardness of two graph coloring games, Traveling salesmen in the presence of competition, Complexity, appeal and challenges of combinatorial games, On variants of vertex geography on undirected graphs, PSPACE-Hardness of some combinatorial games, The complexity of constraint satisfaction games and QCSP, Single-suit two-person card play, On the complexity of connection games, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Complexity of the game domination problem, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, Backgammon is hard, Winner determination algorithms for graph games with matching structures, The shortest connection game, The Complexity of Poset Games, Update games and update networks, Problems on cycles and colorings, A characterization of Zm-well-covered graphs of girth 6 or more, Impartial coloring games, \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\), PSPACE-completeness of two graph coloring games, UNO is hard, even for a single player, Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game, Havannah and TwixT are PSPACE-complete, Maker-breaker total domination game, The complexity of node blocking for dags, Hex ist Pspace-vollständig. (Hex is Pspace-complete), The maker-breaker largest connected subgraph game, Phutball is PSPACE-hard, Single-Player and Two-Player Buttons & Scissors Games, Games on interval and permutation graph representations, A note on first-order projections and games., Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture, The complexity of problems in systems of communicating sequential processes, Game connectivity of graphs, Classifying the computational complexity of problems, On structural parameterizations of Node Kayles, The complexity of two colouring games, The connected greedy coloring game, A combinatorial game over biclique-hypergraphs of powers of paths and of powers of cycles through monochromatic transversals, The Polynomial Profile of Distance Games on Paths and Cycles, Unnamed Item, Unnamed Item, Unnamed Item, Theory of annihilation games. I, The complexity of short two-person games, The complexity of recursion theoretic games, Exact algorithms for Kayles, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Modular Nim, Generalizations of Opt P to the polynomial hierarchy, The complexity of coloring games on perfect graphs, \textsf{PSPACE}-complete two-color planar placement games, A generalization of \textsc{Arc-Kayles}, On the complexity of computing winning strategies for finite poset games, Undirected edge geography, Geography, Complexity of path-forming games, Playing Savitch and Cooking Games, Lower bounds for multiplayer noncooperative games of incomplete information, The diameter game, Unnamed Item, The set coincidence game: Complexity, attainability, and symmetric strategies, Octal games on graphs: the game 0.33 on subdivided stars and bistars, Impartial poker nim, On the shortest path game, A vertex and edge deletion game on graphs, The subset sum game revisited, Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs, Gobang is PSPACE-complete, The largest connected subgraph game, The largest connected subgraph game, An Introduction to Game Domination in Graphs, Compound Node-Kayles on paths, Twenty years of progress of \(\mathrm{JCDCG}^3\), Complexity of path discovery game problems, Simplicial complexes are game complexes, Exact Algorithms for Kayles, Maker-Breaker domination game, \textsf{PSPACE}-hardness of variants of the graph coloring game, Heap games, numeration systems and sequences, On chooser-picker positional games, Recent results and questions in combinatorial game complexities, Colored cut games, Games on triangulations, Prohibiting repetitions makes playing games substantially harder, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete., The complexity of two-player games of incomplete information, Is distributed locking harder?, The Othello game on an \(n\times n\) board is PSPACE-complete, Games against nature, Strings-and-Coins and Nimstring are PSPACE-complete, Decision algorithms for multiplayer noncooperative games of incomplete information, Sprague-Grundy theory in bounded arithmetic
Cites Work
