Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSPACE-COMPLETENESS:
Reports tagged with PSPACE-completeness:
TR99-047 | 10th November 1999
Wolfgang Slany

Graph Ramsey games

We consider combinatorial avoidance and achievement games
based on graph Ramsey theory: The players take turns in coloring
still uncolored edges of a graph G, each player being assigned a
distinct color, choosing one edge per move. In avoidance games,
completing a monochromatic subgraph isomorphic to ... more >>>

TR14-116 | 6th September 2014
Rahul Mehta

2048 is (PSPACE) Hard, but Sometimes Easy

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result
holds for a version of the problem where the player has oracle access to the computer player's moves.
Specifically, we show that for an $n \times n$ game board $G$, computing a
more >>>

TR19-185 | 6th December 2019
Greg Bodwin, Ofer Grossman

Strategy-Stealing is Non-Constructive

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.
This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ... more >>>

ISSN 1433-8092 | Imprint