PSPACE Hardness Reductions in Combinatorial Games

17 concepts10 papers1 proposal

When we think of computationally hard problems, we often think of NP-complete puzzles like Sudoku or the Traveling Salesperson Problem. In these problems, a solver searches for a single, static solution—a valid grid or a short path. But when we transition from solitary puzzles to competitive, two-player games, the nature of complexity changes fundamentally.

In a game, you cannot simply choose a path to victory; you must account for an opponent who actively thwarts you. This alternating dynamic—"I move, then you move, then I move"—mirrors the mathematical structure of quantifiers: $\exists \text{ a move for me such that } \forall \text{ moves by my opponent, } \exists \text{ a counter-move...}$

This infinite chess-like back-and-forth is the hallmark of PSPACE-completeness. Problems in this class can be solved using a memory space that grows polynomially with the size of the board, even though the time required to explore every possible strategy may explode exponentially. To prove that a game is PSPACE-complete, researchers use gadget reductions: they build modular components within the game's rules that act like logical gates, translating abstract boolean formulas into physical or topological constraints on the board.

The Engine of Hardness: Quantifier Alternation

The canonical PSPACE-complete problem is the Quantified Boolean Formula (QBF) problem, where players effectively take turns assigning truth values to variables to either satisfy or falsify a logical formula. To prove a combinatorial game is PSPACE-complete, a researcher must show that any QBF instance can be simulated by playing that game.

[QBF Formula] ---> [Reduction Compiler] ---> [Game Instance]
(Alternating        (Variable & Clause        (Graph, Board,
 Quantifiers)        Gadgets)                  or Card Layout)

In his analysis of the path-extension game Tron, a combinatorial Game on abstract Graphs, Tillmann Miltzow demonstrates this exact mechanism. By constructing specific graph structures called "visages," Miltzow built variable and clause gadgets directly out of the graph's vertices and edges.

  • Variable Gadgets force players into a binary choice (e.g., moving left represents setting a variable to True, moving right sets it to False).
  • Clause Gadgets act as checkpoints that can only be traversed if at least one of the chosen paths satisfies the underlying logical clause.

If the second player can trap the first player within these gadgets, it means the original formula was unsatisfiable. Thus, determining if a winning strategy exists is perfectly equivalent to solving the QBF.

From Geometric Boards to Abstract Graphs

This framework applies across wildly different game environments, from geometric grids to topological networks.

Geometric Constraints

In board games like Amazons, players move pieces and burn squares to block their opponent's movement. Timothy Furtak et al. proved in Generalized Amazons is PSPACE-Complete that even a simplified version of the game with only one piece per player remains PSPACE-complete. They achieved this by designing geometric gadgets where the physical layout of the board restricts piece movement in a way that perfectly emulates the flow of truth values through a boolean circuit.

Topological Connectivity

Instead of blocking physical space, many modern graph games focus on connectivity. In The Largest Connected Subgraph Game, Julien Bensmail et al. explored a scenario where players alternate coloring vertices to claim the largest monochromatic connected component. To prove its hardness, the authors bypassed QBF and reduced from POS CNF—a logic problem where variables are strictly positive—mapping formula satisfaction directly into graph connectivity structures.

Even when the game is simplified into a Maker-Breaker format—where one player tries to build a structure and the other purely tries to ruin it—the complexity remains daunting. In The Maker-Breaker Largest Connected Subgraph game, Julien Bensmail et al. proved that determining the winner is PSPACE-complete even on highly restricted graph classes like planar or bipartite graphs. They achieved this by reducing from planar generalized Hex, showing that the adversarial struggle to connect a path survives even when the graph's topology is severely flattened.

The Universality of the Alternation Mechanism

The power of gadget reductions is their ability to reveal identical complexity profiles in games that appear completely unrelated on the surface.

+-----------------------------------------------------------------------+
|                      PSPACE-Complete Games                            |
+-----------------------------------------------------------------------+
|  [Graph Traversal]      [Card Games]       [Network Security]         |
|  Tron (Miltzow)         Durak (Bonnet)     Colored Cuts (Morawietz)   |
+-----------------------------------------------------------------------+
|                 Shared Underlying Mechanism:                          |
|   Adversarial turn-taking maps to alternating logical quantifiers     |
+-----------------------------------------------------------------------+

Card Games

Consider the Russian card game Durak. While it features attack-defense card play rather than board positioning, Edouard Bonnet proved in The Complexity of Playing Durak that a perfect-information variant of the game is PSPACE-complete. The tactical back-and-forth of defending against card attacks functions exactly like the variable-claiming steps in a logical formula reduction.

Network Security

The same mathematical engine models defensive scenarios. In Colored Cut Games, Nils Morawietz et al. analyzed a game where an attacker deletes colored edges to disconnect a network, while a defender protects specific colors. By reducing from the COMPETITIVE HITTING SET problem, the authors demonstrated that an unbounded number of strategic alternations between an attacker and a defender inherently forces PSPACE-completeness.

Edge Selection, Coloring, and Scoring

This hardness persists across various rule variations:

  • Edge-Claiming: Éric Duchêne et al. showed in Complexity of Maker-Breaker games on edge sets of graphs that trying to force specific subgraphs (like a perfect matching) by claiming edges is PSPACE-complete due to reductions from logic-based games.
  • Orthogonal Coloring: In The Complexity of Two Colouring Games, Stephan Dominique Andres et al. proved that coloring vertices across twin graphs under unique pairing constraints is PSPACE-complete for both standard win conditions and scoring variants.
  • Mathematical Scoring: Even arithmetic graph games fall into this class. Éric Duchêne et al. demonstrated in Smash and grab: The 0 ⋅ 6 scoring game on graphs that calculating optimal strategies in generalized scoring games remains PSPACE-complete on arbitrary graphs.

Boundaries of the Complexity Landscape

What happens when we alter the structural freedom of the players? The complexity can either skyrocket or collapse.

If a game allows players to revisit states or move indefinitely without progress, the state space can expand beyond polynomial memory boundaries. For example, Harmender Gahlawat et al. showed in Romeo and Juliet Is EXPTIME-Complete that a pursuit-evasion game on general graphs is EXPTIME-complete because the players can move along cycles indefinitely. However, when they restricted the game to Directed Acyclic Graphs (DAGs)—where time and movement flow strictly forward—the complexity dropped back down to PSPACE-complete.

Ultimately, these papers show that PSPACE-completeness is not a property unique to specific board layouts or card decks. Instead, it is the natural computational consequence of adversarial turn-taking in a finite space. By using gadget reductions, computer scientists prove that playing an optimal game is fundamentally the same as evaluating the truth of a deeply nested logical proposition.

Key Foundational Work

Tron, a combinatorial Game on abstract Graphs (2011) — contributed 2 concept elements to this direction.
Generalized Amazons is PSPACE-Complete (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pspace_completeness_reduction_4721a3e9,
  title = {PSPACE-completeness reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pspace-completeness-reduction/rdr_4721a3e95a23481e8011af225b6a254a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_pspace_completeness_reduction_4721a3e9_v1,
  title = {PSPACE-completeness reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pspace-completeness-reduction/rdr_4721a3e95a23481e8011af225b6a254a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake