All results and sources

Even without new random tiles, reaching 2048 can encode satisfiability.

NP: completeness

Exact task

Can a tile of value 2048 be formed from the supplied grid when no new tiles ever appear?

Scale & input

Arbitrary m × n board with given power-of-two tiles; target 2048.

Move rules

Slide all tiles in a chosen direction; matching tiles merge once per move.

Goal

Create a tile of value 2048.

Repetition

Revisits allowed; polynomial certificates established between merges.

Players & information

One player; whole board visible.

Randomness

No spawned tiles.

This is the no-new-tiles variant, not the ordinary random-spawn game on 4 × 4.

Open this result in the map

Bulb placements can encode an entire Boolean circuit.

NP: completeness

Exact task

Can lamps illuminate every white cell without shining on one another, while meeting every numbered adjacency clue?

Scale & input

Variable rectangle with black walls and numbered clues.

Move rules

Bulbs shine along rows/columns until walls; bulbs cannot see one another.

Goal

Light every white cell and satisfy adjacent-bulb counts.

Repetition

Static placement.

Players & information

One solver; full puzzle visible.

Randomness

None.

Counts are orthogonal neighbors, not all illuminated cells.

Open this result in the map

Every unnumbered layout can be completed by adding a bulb to an unlit cell until none remain.

P: polynomial-time algorithm

Exact task

Can lamps illuminate every white cell without shining on one another when there are no numbered clues?

Scale & input

Growing grid; unnumbered black walls only.

Move rules

Same lighting and nonvisibility rules.

Goal

Illuminate all white cells.

Repetition

At most one new bulb per step.

Players & information

All cells known.

Randomness

None needed.

A primary undergraduate thesis; the short greedy proof is explicit.

Open this result in the map

Force bulbs around each 4, reject conflicts, then greedily light dark cells.

P: polynomial-time algorithm

Exact task

Decide whether the puzzle can be completed.

Scale & input

Growing grid. Walls are unnumbered or labeled 4.

Move rules

Ordinary Akari lighting and bulb-count rules.

Goal

Light every white cell without bulbs seeing each other.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

Primary undergraduate thesis. Forced-bulb conflicts must be checked.

restriction: Akari / Light Up · Can the whole board be lit?. This comparison is not itself a reduction.

Open this result in the map

Each of these three fixed clue sets still encodes circuits.

NP: completeness

Exact task

Decide whether the puzzle can be completed.

Scale & input

Growing grid. Choose one allowed number: 1, 2, or 3. Unnumbered walls also allowed.

Move rules

Ordinary Akari lighting and bulb-count rules.

Goal

Light every white cell and meet each clue.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

Primary undergraduate thesis with mechanically checked gadgets.

restriction: Akari / Light Up · Can the whole board be lit?. This comparison is not itself a reduction.

Open this result in the map

A queen-like move followed by a blocking arrow can implement logical wires and gates.

PSPACE: completeness

Exact task

Decision: can the player to move force a win?

Scale & input

Arbitrary n×n position with a growing number of amazons.

Move rules

Move an amazon as a chess queen, then shoot a queen-moving arrow that permanently blocks its destination. No captures.

Goal

Opponent has no legal move.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The proof uses many amazons. It is not a hardness proof for only four per side.

Open this result in the map

Even with those future choices disclosed, finding a winning play is NP-hard.

NP: hardness / lower bound

Exact task

Can you win against this prescribed opponent and roll sequence?

Scale & input

Explicit scalable line of points and polynomially many checkers. Six home points per side and two six-sided dice suffice. Input includes the prescribed future rolls and opponent policy.

Move rules

Move according to both dice, doubles four times. Two opposing checkers block a point. A hit checker must re-enter before others move.

Goal

Bear off every checker first.

Repetition

Captures permit arbitrarily long play. No fixed turn limit is assumed.

Players & information

Two players, with the opponent’s complete policy revealed in this task.

Randomness

Both players’ future rolls are supplied, using the paper’s compact descriptions.

Hardness only. This is neither a fixed 24-point board nor expected win probability under fair random dice.

Open this result in the map

The opponent now chooses variable assignments in the reduction.

PSPACE: hardness / lower bound

Exact task

Can you force a win against an opponent whose policy is not disclosed?

Scale & rules

Same scalable checker/point model and known roll schedule. Both players choose strategically.

Result scope

Theorem 2 is a hardness result. It does not prove PSPACE membership.

rule change: Replace the prescribed opponent by an adversarial player · Backgammon · Known rolls & opponent. This comparison is not itself a reduction.

Open this result in the map

The proof uses roll choices that adapt to play to simulate a revisitable formula game.

EXPTIME: hardness / lower bound (Adversarially adaptive rolls in the source model. Hardness only, not fair-dice probability or completeness.)

Exact task

What is the hardness of the paper’s unknown-strategy, unknown-roll winner model?

Scale & rules

Same generalized board. Opponent and future rolls are unknown, with adaptively chosen rolls in the reduction.

Randomness

No expected-score or specified probability threshold is analyzed.

The theorem concerns adaptive rolls, not fair-dice win probabilities. It proves EXPTIME-hardness without a matching upper bound.

rule change: Allow an adversarial strategy and adaptive future rolls · Backgammon · Known rolls & opponent. This comparison is not itself a reduction.

Open this result in the map

The author explicitly leaves membership questions open.

Open question in 2021 source

Exact task

Which upper bounds match the three backgammon hardness models?

Scope

KSKR, USKR and USUR exactly as defined in the paper. Future-policy and roll encodings must be specified.

Caution

An unbounded game length alone does not rule out EXPTIME algorithms on finitely represented game graphs.

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Ask for membership, not only hardness · Backgammon · Known rolls & opponent. This comparison is not itself a reduction.

Open this result in the map

Ships and water encode Boolean choices.

NP: completeness

Exact task

Does any fleet placement satisfy all supplied clues and row/column totals?

Scale & input

Growing rectangular grid, partial ship/water clues, totals and fleet. Ship lengths and fleet size may grow.

Move rules

Ships are straight, width one, horizontal or vertical. Distinct ships may not touch, even diagonally.

Goal

Place the full fleet and meet every clue.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

Solitaire logic puzzle, not the two-player hidden-fleet guessing game. General fleet, not a fixed commercial fleet.

Open this result in the map

Uniqueness alone does not supply an efficient solving algorithm.

NP: hardness / lower bound (Promise search problem. Hardness uses randomized reductions, not randomness in puzzle play.)

Exact task

Find the unique fleet placement.

Scale & input

Growing grid and general fleet, as in the decision problem. Exactly one solution promised.

Move rules

Same fleet, clue and no-touch conditions.

Goal

Output the promised solution.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

A promise search problem, not NP-completeness of an always-yes existence question. Randomness is in the reduction, not puzzle play.

task change: Battleships solitaire · Can the fleet fit the clues?. This comparison is not itself a reduction.

Open this result in the map

Changing a 1×1×2 rolling block into a unit cube makes this reachability problem polynomial-time.

PSPACE: completeness

Exact task

Can the block legally reach the goal standing upright?

Scale & input

Explicit list of board tiles, start/goal, bridge states and one-to-one switch-to-bridge links.

Move rules

Roll/tilt a 1×1×2 block. Entering a switch toggles its bridge. All occupied cells must be supported.

Goal

Reach the goal upright.

Repetition

Revisits and repeated switch activation allowed.

Players & information

One player. Complete board state known.

Randomness

None.

Scalable levels with switches and bridges only. No splitting portals or weak tiles required.

Open this result in the map

Only polynomially many block positions and orientations remain.

P: polynomial-time algorithm

Exact task

Decide whether the rolling block can reach the goal.

Scale & input

Explicit finite board with a 1×1×2 block, start and goal.

Move rules

Roll and tilt, always fully supported. Static tiles only.

Goal

Reach goal upright.

Repetition

Revisits allowed.

Players & information

One player. Complete board known.

Randomness

None.

restriction: Bloxorz · Reach the goal with switches and bridges. This comparison is not itself a reduction.

Open this result in the map

A unit cube can expand its reachable area systematically.

P: polynomial-time algorithm

Exact task

Decide whether the cube can reach the goal using switches and bridges.

Scale & input

Same explicit switch/bridge board, with a 1×1×1 cube.

Move rules

Step to an adjacent supported square, toggling switches.

Goal

Reach goal.

Repetition

Revisits and repeated toggles allowed.

Players & information

One player. Full state known.

Randomness

None.

rule change: Bloxorz · Reach the goal with switches and bridges. This comparison is not itself a reduction.

Open this result in the map

A tile that disappears after use can enforce Boolean choices.

NP: completeness

Exact task

Decide whether the 1×1×2 block can reach the goal.

Scale & input

Explicit board. Normal and single-use tiles, no switches or bridges.

Move rules

Roll/tilt long block. Fragile tiles disappear after traversal.

Goal

Reach goal upright.

Repetition

Fragile tiles cannot be reused.

Players & information

One player. Full board known.

Randomness

None.

Single-use tiles are a theoretical variant, not a feature of the original Bloxorz.

rule change: Bloxorz · Reach the goal with switches and bridges. This comparison is not itself a reduction.

Open this result in the map

A cascade can encode a logical choice. Which columns fall determines whether one chosen gem can ever be matched.

NP: hardness / lower bound

Exact task

Can a sequence of legal swaps pop the designated gem?

Scale & input

Arbitrary rectangular board; six gem types; all replacement gems known beforehand.

Move rules

Swap adjacent gems to form matches. Matching lines disappear simultaneously, gravity acts, and cascades resolve.

Goal

Pop one designated gem.

Repetition

No imposed move-count bound; later swaps may revisit locations.

Players & information

One player; entire board and replenishment information available.

Randomness

Offline prescribed replenishment, not random unknown future gems.

The formal theorem establishes NP-hardness. This is not an expected-score claim about the commercial random game.

Open this result in the map

Requiring a capture every turn bounds the game’s length, but optimal play remains PSPACE-complete.

PSPACE: completeness

Exact task

Decision: can the first player force a win?

Scale & input

Supplied n×n position.

Move rules

Mandatory jumps; continue the capture sequence while possible. Kings jump in either direction.

Goal

Opponent cannot jump.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Noncapturing moves are forbidden, even when no capture exists.

Open this result in the map

Cooperation changes the always-jumping game into a solution-existence puzzle.

NP: completeness

Exact task

Decision: can cooperating players eliminate one color?

Scale & input

Supplied n×n position.

Move rules

Alternate mandatory capturing turns; continue available jumps.

Goal

Remove every piece of either color.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two sides cooperate; complete information.

Randomness

None.

This claim concerns the always-jumping variant.

Open this result in the map

Losing immediately is computationally hard even though the horizon is only two turns.

NP: completeness

Exact task

Can you make a move forcing the opponent to capture all your remaining pieces next turn?

Model & rules

Arbitrary position on a growing n×n board. American checkers captures are compulsory and must continue while possible. Kings jump in both directions. Two players, full information, no randomness. Only the next two turns are relevant.

task change: Ask for an immediate forced loss · Checkers · Every turn must capture. This comparison is not itself a reduction.

Open this result in the map

Replacing forced capture with a cooperative choice remains NP-complete.

NP: completeness

Exact task

Can your move let the opponent capture all your pieces on their next turn?

Model & rules

Arbitrary position on a growing n×n board. American checkers captures are compulsory and must continue while possible. Kings jump in both directions. Two players, full information, no randomness. Only the next two turns are relevant.

task change: The opponent helps instead of resisting · Force your opponent to capture everything. This comparison is not itself a reduction.

Open this result in the map

Ordinary piece movements can encode repeatedly changing logical variables.

EXPTIME: completeness

Exact task

Decision: can the designated player force a win?

Scale & input

Arbitrary n×n position; one king per side; numbers of other pieces grow with n.

Move rules

Standard movement and capture of the chess pieces used in the construction.

Goal

Force the opponent’s king into checkmate.

Repetition

Unbounded-play model: no polynomial draw clock; endless play is not a forced win.

Players & information

Two players; all information visible.

Randomness

None.

Not a theorem about fixed 8×8 chess, modern move-count draw rules, or reachability from the standard opening.

Open this result in the map

Even cooperative chess can require solving a PSPACE-complete reachability problem.

PSPACE: completeness

Exact task

Can any legal sequence checkmate Black?

Scale & input

Explicit growing n×n position, arbitrary number of pieces, exactly one king per color.

Move rules

Standard piece moves and alternating turns, with kings never left in check.

Players & information

Two cooperating players, full information.

Randomness

None.

Repetition

Unbounded reachability problem. No polynomial move limit or automatic tournament draw counter is part of the paper’s state definition.

This is the paper’s unbounded-sequence model. Its state does not include tournament move-count or repetition counters. Automatic-draw variants require a separate classification.

task change: Replace forced mate with possible mate · Chess · Force checkmate. This comparison is not itself a reduction.

Open this result in the map

Testing reachability itself is hard, before asking which earlier move was forced.

PSPACE: completeness

Exact task

Is the input position reachable from a natural generalized starting setup?

Scale & input

Explicit growing n×n position, arbitrary number of pieces, exactly one king per color.

Move rules

Standard piece moves and alternating turns, with kings never left in check.

Players & information

Two cooperating players, full information.

Randomness

None.

Repetition

Unbounded reachability problem. No polynomial move limit or automatic tournament draw counter is part of the paper’s state definition.

Start condition

First two and last two ranks filled, pawns on the inner ranks, one king and sufficiently many other non-pawn types on each outer rank, middle empty.

The starting family is defined in the paper, not a unique standard 8×8 opening. The unbounded sequence model does not impose tournament draw counters.

task change: Replace checkmate with a specified position · Cooperate to reach checkmate. This comparison is not itself a reduction.

Open this result in the map

Every rectangle with more than one square is a first-player win by strategy stealing.

P: polynomial-time algorithm

Exact task

Who wins from a complete rectangular chocolate bar?

Scale & input

Positive dimensions m,n given in binary or unary, describing a full rectangle.

Move rules

Choose a remaining square and remove it and every square up and to its right. The lower-left square is poisoned.

Goal

Make the opponent take the poison.

Repetition

Each move removes at least one square.

Players & information

Two players, perfect information.

Randomness

None.

This decides the winner. The proof does not provide an efficient winning first move. The 1×1 board is losing.

Open this result in the map

This search question is explicitly open even though deciding who wins is immediate.

PSPACE: upper bound / membership (Polynomial-space search for a winning opening move on unary rectangles.) · Open question in 2020 source

Exact task

Can a winning first move be found in polynomial time in unary dimensions?

Input & rules

A full m×n rectangle with m,n written in unary, at least two cells. Same poison and bite rules.

Scope

The authors place the search in polynomial space and explain why the sparse input is an obstacle to usual hardness proofs.

This records the question in the cited 2020 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Find a move rather than name the winner · Chomp · Winner on a full rectangle?. This comparison is not itself a reduction.

Open this result in the map

Hardness of unrestricted poset games does not settle their two-dimensional Chomp restriction.

PSPACE: upper bound / membership (Explicit partially eaten position, at most one move per remaining cell.) · Open question in 2013 source

Exact task

What is the winner-decision complexity for arbitrary Chomp positions?

Input & rules

Explicit remaining cells of a downward-closed chocolate shape with the poison retained, not a succinct exponentially large bar. Same bite rule.

Upper bound

In PSPACE by finite board storage and at most one move per cell.

This records the question in the cited 2013 source, not a lower bound or a claim that every variant of this game is unresolved.

rule change: Allow a partially eaten starting position · Chomp · Winner on a full rectangle?. This comparison is not itself a reduction.

Open this result in the map

Polynomial-space search follows from the move bound. Exact complexity is open in the cited source.

PSPACE: upper bound / membership

Exact task

Can the player to move force a win?

Scale & input

A finite grid-cell board supplied explicitly, possibly with unavailable cells, plus the player to move.

Move rules

One player places vertical dominoes and the other horizontal dominoes. Occupied cells cannot be reused.

Goal

Make the last legal move.

Repetition

Every move consumes two empty cells, so play has at most N/2 moves.

Players & information

Two players, deterministic perfect information.

Randomness

None.

The 2026 graph-generalization results do not automatically settle domino placement on a grid.

Open this result in the map

The authors explicitly identify general-board winner complexity as open.

PSPACE: upper bound / membership (Explicit finite grid, at most one domino placement per two cells, as recorded in the assumptions.) · Open question in 2024 source

Exact task

Is deciding the Domineering winner efficiently solvable, or can hardness be proved?

Rules

Explicit remaining grid cells. Vertical versus horizontal placement, normal play.

Known upper bound

In PSPACE by at most N/2 moves.

This records the question in the cited 2024 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Close the upper/lower-bound gap · Domineering · Winner from a position?. This comparison is not itself a reduction.

Open this result in the map

The general-board problem is explicitly open. The simple parity strategies for some empty rectangles do not settle it.

PSPACE: upper bound / membership (Explicit finite grid, at most one domino placement per two cells, as recorded in the assumptions.) · Open question in 2024 source

Exact task

What is the complexity of deciding the Cram winner on a general grid board?

Rules

Explicit remaining grid cells. Both players may place a horizontal or vertical domino. No overlap, last move wins.

Bound

At most N/2 moves, hence polynomial-space search.

This records the question in the cited 2024 source, not a lower bound or a claim that every variant of this game is unresolved.

rule change: Allow both orientations for both players · Domineering · Winner from a position?. This comparison is not itself a reduction.

Open this result in the map

A September 2026 proof settles the unrestricted graph game.

PSPACE: completeness

Exact task

Who wins when domino placements are graph edges?

Scale & rules

Explicit finite undirected graph. A move selects an edge and removes its two endpoints. The last move wins.

Players & information

Two players, perfect information, no randomness, at most |V|/2 moves.

This does not prove PSPACE-hardness of grid Cram.

rule change: Remove orientation ownership and replace the grid by a graph · Domineering · Winner from a position?. This comparison is not itself a reduction.

Open this result in the map

A movable tire and icy slope act as a switch that opens or closes a route.

PSPACE: completeness

Exact task

Can the player reach the designated goal from the supplied start?

Scale & input

Stage size and remembered state scale; not a fixed commercial stage.

Move rules

One Kong; rolling tires, ice, ropes, barrel cannons and Zingers.

Goal

Reach a designated goal from the start.

Repetition

Revisits allowed.

Players & information

One player; fully specified stage.

Randomness

Deterministic enemy patterns in the construction.

Idealized glitch-free rules; a fixed screen with resetting state is a different model.

Open this result in the map

The pencil-and-paper game can encode competing choices of variables in a logical formula.

PSPACE: completeness

Exact task

Decision: can the player to move force a higher final score?

Scale & input

Growing rectangular grid; existing lines, scores and turn supplied.

Move rules

Draw an unused unit edge. Completing a box scores a point and grants another turn.

Goal

Higher score when every edge is drawn.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Scores are part of the supplied position. This does not classify the empty-board opening alone.

Open this result in the map

The proof permits parallel strings and nonplanar graphs. This is broader than an ordinary square board.

PSPACE: completeness

Exact task

Who wins when the first player unable to cut a string loses?

Model & rules

Explicit multigraph with grounded strings allowed. Two players cut one string. Freeing a coin forces another cut. Full information, no randomness. Strings disappear permanently.

rule change: Use normal play on arbitrary multigraphs · Dots & Boxes · More boxes than your opponent?. This comparison is not itself a reduction.

Open this result in the map

The multigraph hardness construction does not settle this restriction.

Open question in 2021 source

Exact task

Determine the winner under Nimstring scoring-free rules on grid instances.

Model & rules

Growing ordinary Dots & Boxes grid viewed as its strings-and-coins dual. Keep extra turns for completed boxes, but the first player unable to move loses. Two players, full information, no chance, no reused edge.

Open in the cited 2021 source. Later status is not established by this record.

restriction: Require ordinary grid instances · Nimstring: change how the winner is chosen. This comparison is not itself a reduction.

Open this result in the map

Allowing paths to zigzag freely does not remove the hardness.

NP: completeness

Exact task

Can pairwise disjoint paths join the terminal pairs and cover every cell?

Scale & input

Explicit n×n grid. The number of distinct terminal pairs grows.

Move rules

Orthogonal simple paths, one per pair. Every cell belongs to exactly one path.

Goal

Join all matching terminals and cover the grid.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

No minimum-turn rule. The claim is not about a fixed app level.

Open this result in the map

This is the tractable rectangular-grid Hamiltonian path problem.

P: polynomial-time algorithm

Exact task

Decide whether a path joins the two terminals and visits every cell.

Scale & input

Full m×n rectangle and exactly two designated endpoints. No holes.

Move rules

One simple orthogonal path.

Goal

Cover every cell between the endpoints.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

restriction: Flow Free / Numberlink · Connect every pair and cover every cell. This comparison is not itself a reduction.

Open this result in the map

One pair is tractable. The hardness proof uses many pairs. The authors ask whether every fixed pair count is tractable, and whether the pair count gives an FPT algorithm.

Open question in 2015 source

Exact task

Decide whether all pairs can be connected while filling the entire rectangle, with the number of pairs fixed.

Scale & input

An arbitrarily large explicit rectangular grid with k pairs of terminals, k fixed independently of grid size.

Move rules

Orthogonal paths may turn freely, cannot cross or share cells, and must cover every cell.

Goal

Connect each matching pair and fill the board.

Repetition

Paths are simple.

Players & information

One solver, complete information.

Randomness

None.

Open in the cited 2015 source; later status is not established by this record. A no-self-touching, uniqueness-promised solver is a different problem.

restriction: Fix the number of pairs · Flow Free / Numberlink · Connect every pair and cover every cell. This comparison is not itself a reduction.

Open this result in the map

Move along arrows without returning to a visited vertex. Deciding who can force the last legal move is PSPACE-complete.

PSPACE: completeness

Exact task

Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given directed graph of arbitrary size and a starting vertex.

Move rules

Players alternate moving one shared token along an outgoing arrow to an unvisited vertex.

Goal

A player with no legal move loses.

Repetition

Vertices cannot be revisited; at most |V|−1 token moves.

Players & information

Two players; Perfect information

Randomness

None

The source counts placing the initial marker as a turn; specifying who moves next, or adding a forced prefix, translates conventions.

Open this result in the map

Make the paths two-way and keep the ban on revisiting vertices. Maximum matching now gives a polynomial-time winner algorithm.

P: polynomial-time algorithm

Exact task

Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given undirected graph of arbitrary size and a starting vertex.

Move rules

Move the shared token to a neighbor, deleting the vertex just left.

Goal

A player with no legal move loses.

Repetition

No vertex revisits.

Players & information

Two players; Perfect information

Randomness

None

The player to move wins exactly when every maximum matching covers the token's vertex. Compare maximum-matching sizes in G and G−v.

Open this result in the map

Still use two-way paths, but use up each edge rather than each vertex. Vertices can be revisited, and winner determination is PSPACE-complete again.

PSPACE: completeness

Exact task

Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given undirected graph of arbitrary size and a starting vertex.

Move rules

Move the shared token along an unused edge, then delete that edge.

Goal

A player with no legal move loses.

Repetition

Edges cannot be reused; vertices may be revisited. At most |E| moves.

Players & information

Two players; Perfect information

Randomness

None

Hardness persists on planar graphs of maximum degree 3. Bipartite graphs admit a polynomial algorithm.

Open this result in the map

Hardness survives even when edges can be drawn without crossings and every vertex has at most three neighbors.

PSPACE: completeness

Exact task

Decision: can the next player force a win?

Scale & input

Directed planar bipartite graph, maximum total degree three; start vertex supplied.

Move rules

Move to an unvisited out-neighbor.

Goal

Opponent has no move.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Directions still matter. This is not undirected vertex Geography.

Open this result in the map

Degree three permits efficient nimber computation. Degree four already gives PSPACE-hardness, while recursive computation still needs only polynomial space.

P: polynomial-time algorithm (Compute the Grundy-value function on explicit graphs of maximum degree 3.) · PSPACE: hardness / lower bound (Grundy-value computation on explicit graphs of maximum degree 4. This is a function hardness result, not a PSPACE-complete decision-language claim.) · PSPACE: upper bound / membership (Polynomial-space computation of the Grundy-value function by depth-first mex evaluation.) [atlas-derived]

Exact task

Compute an undirected Geography position's Grundy value.

Model & rules

Explicit graph and token. Alternate to unvisited neighbors. The player with no legal move loses. Perfect information, no randomness.

Open this result in the map

Each board alone is easy. Their combined game is hard.

PSPACE: completeness

Exact task

Determine the winner of two undirected Geography positions combined.

Model & rules

Two explicit graphs and tokens. Each turn moves on exactly one board to an unvisited neighbor. A player unable to move on either board loses. Perfect information, no randomness.

Open this result in the map

Adding one shared pass makes winner determination PSPACE-complete.

PSPACE: completeness

Exact task

Determine the winner with one pass available to either player.

Model & rules

Explicit undirected graph and token. Move to an unvisited neighbor or consume the shared pass. Passing is allowed even when stuck. A player with no remaining action loses. Perfect information, no randomness.

Open this result in the map

Pass parity matters: one pass is PSPACE-complete, two passes give the original polynomial-time winner test.

P: polynomial-time algorithm

Exact task

Determine the winner with exactly two shared passes available.

Model & rules

Explicit undirected graph and token. Move to an unvisited neighbor or consume one of two shared passes, including when stuck. Two players, full information, no randomness. Every action removes a vertex or pass. The player with no legal action loses.

rule change: Increase the shared pass allowance from 1 to 2 · One shared pass changes the winner problem. This comparison is not itself a reduction.

Open this result in the map

Even constructions without ko battles encode a hard strategy problem.

PSPACE: hardness / lower bound

Exact task

Can Black force a win from the supplied generalized Go position under the paper’s scoring and pass rules?

Scale & input

Variable n×n board; a supplied stone position.

Move rules

Place stones, capture surrounded groups, or pass.

Goal

Territory minus captured own stones; two passes end play.

Repetition

The hardness construction avoids ko; no claim about equivalence of repetition rules.

Players & information

Two players; all information visible.

Randomness

None.

This is the paper’s ko-free hardness construction, not a complete classification of every modern Go ruleset.

Open this result in the map

Hardness survives a hand of two cards and at most two copies of each card.

NP: completeness

Exact task

Can one player complete every color sequence?

Scale & input

Explicit ordered deck, scalable number of colors and values. Hand capacity h=2 and multiplicity at most 2 suffice.

Move rules

Scan the known deck. Play, discard or store each card. Play each color in increasing order without skipping numbers.

Goal

Play values 1 through n in every color.

Repetition

The finite deck is processed once. Discards are permanent.

Players & information

One player with full knowledge of every card and draw order.

Randomness

None. The order is input, not a fresh random draw.

This is the paper’s solitaire planning model, not an exact classification of normal hidden-hand multiplayer Hanabi.

Open this result in the map

A near-linear algorithm chooses which copies to save.

P: polynomial-time algorithm

Exact task

Can the known deck be completed with one color?

Scale & rules

Same solitaire model, one color, arbitrary finite hand capacity and duplicates.

restriction: Restrict the deck to one color · Hanabi · Known-deck solitaire. This comparison is not itself a reduction.

Open this result in the map

A greedy linear-time test suffices.

P: polynomial-time algorithm

Exact task

Can the deck be completed if each card appears once?

Scale & rules

Same full-information solitaire model. Multiplicity is exactly one or less, colors and values may scale.

restriction: Remove duplicate copies · Hanabi · Known-deck solitaire. This comparison is not itself a reduction.

Open this result in the map

Ring threats simulate a walk through a Geography graph.

PSPACE: completeness

Exact task

Decision: can the designated player force a winning shape?

Scale & input

A given position on a hexagonal board of growing side length.

Move rules

Add one stone of the player’s color to an empty cell. Stones never move or get captured.

Goal

Make a ring enclosing a cell, connect two corners, or connect three sides. Corners do not count as sides.

Repetition

Every turn fills a new cell.

Players & information

Two players, full information. The input is a played position, not a claim about empty-board strategy.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

Open this result in the map

From a supplied partly filled board, deciding who can force a connection is PSPACE-complete as the board grows.

PSPACE: completeness

Exact task

Does the player to move have a winning strategy from the supplied partly filled board?

Scale & input

An n×n rhombus of hexagonal cells, with n part of the input; arbitrary supplied positions.

Move rules

Alternate placing a stone of your color on an empty cell. No swap/pie rule.

Goal

Connect your assigned opposite sides with your stones.

Repetition

Stones never move or disappear; no cell is played twice.

Players & information

Two players; Perfect information

Randomness

None

This classification does not concern only a fixed 11×11 commercial board, or only empty starting boards.

Open this result in the map

On every empty square Hex board without a swap rule, the first player has a winning strategy. This settles the winner question, not how to play the winning moves.

P: polynomial-time algorithm

Exact task

On an empty n×n board without the swap rule, does the first player have a winning strategy?

Scale & input

Empty square rhombus boards of every size n≥1.

Move rules

The same placement and connection rules as Hex; no swap/pie rule.

Goal

Connect your assigned opposite sides with your stones.

Repetition

Stones remain fixed; a cell can be filled only once.

Players & information

Two players; Perfect information

Randomness

None

The decision answer is always yes. Strategy stealing establishes existence; this is not an efficient method for finding the winning moves.

Open this result in the map

Knowing that the first player wins does not identify the move. The paper leaves polynomial-time search open for Hex itself.

Open question in 2020 source

Exact task

Given the empty board's dimensions in unary, output a winning first move.

Model & rules

Empty growing square Hex board, normal alternating placement and connection goals, no swap rule. Two players, perfect information, no randomness. Cells are never reused.

Its PSPACE-hardness theorem covers broader game classes, not this empty-Hex search problem. Open status is dated to the cited paper.

Open this result in the map

For ordinary planar Hex, the dependence on board size can be polynomial with the expensive part confined to k.

FPT: parameterized result (Fixed-parameter tractable in input turn bound k. Not a polynomial-time claim when k varies freely.)

Exact task

Can the player force a connection within k total plies?

Model & rules

Growing explicit Hex board and input bound k on total alternating moves. Existing stones allowed, usual connection goals. Full information, no randomness. Each turn fills one cell.

FPT is not a claim of polynomial time when k varies freely. The proof’s dependence on k is not practical.

task change: Bound the winning horizon · Hex · From a given position. This comparison is not itself a reduction.

Open this result in the map

The authors ask whether small strategies must exist even when finding them is hard.

Open question in 2020 source

Exact task

Does empty-board Hex necessarily admit a polynomial-size optimal-strategy circuit?

Scope

A scalable empty symmetric Hex board. A circuit takes a reached position and outputs the strategy’s next move.

Distinction

This is strategy representation size, not the problem of finding one opening move.

This records the question in the cited 2020 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Ask for a compact whole-game strategy · Hex · From an empty board. This comparison is not itself a reduction.

Open this result in the map

The requirement that pieces remain connected can lock other pieces in place and encode logical choices.

PSPACE: hardness / lower bound · EXPTIME: upper bound / membership (Atlas-derived finite-state exponential-time upper bound under this record’s explicit rules.) [atlas-derived]

Exact task

In the multi-queen n-Hive generalization, can a specified player force a win?

Scale & input

n-Hive: growing equal piece sets, including multiple queens. All pieces already placed in the proof. The supplied position is a legal connected hive.

Move rules

Usual piece movements, One Hive and Freedom To Move rules. A player with no legal placement or movement must pass.

Goal

Surround any opposing queen. Simultaneous loss is a draw.

Repetition

No move cap or repetition prohibition is imposed.

Players & information

Two players; all information visible.

Randomness

None.

Publication status

Published in FUN 2026 proceedings on May 15, 2026.

The EXPTIME upper bound is a finite-state consequence derived here, not a theorem asserted by the source. The multi-queen generalization and no history-dependent repetition rule are essential. Ordinary commercial Hive is a fixed finite game.

Open this result in the map

Ambiguous tab-and-pocket matches make scalable assembly NP-complete.

NP: completeness

Exact task

Can all supplied pieces assemble into the target square?

Scale & input

An explicit finite collection of n nearly square pieces and a target square. Shapes are encoded by finitely described matching types.

Move rules

Face-up orthogonal placement of tab-and-pocket pieces, matching shapes only. Use each supplied piece once.

Goal

Fill the target exactly, without overlap or gaps.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

This concerns scalable, potentially ambiguous piece sets, not the difficulty of a particular commercial picture puzzle.

Open this result in the map

Exact edge matching is NP-complete and converts to jigsaw assembly.

NP: completeness

Exact task

Can all colored-edge tiles fill the target square?

Scale & input

n explicitly listed unit-square tiles, with four colors per tile and a square target of area n.

Move rules

Place tiles on the square grid. Adjacent edge colors must agree. Every tile is used exactly once.

Goal

Fill the target with compatible edges.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

The reduction forces tile orientations. Difficulty does not rely on image recognition.

Open this result in the map

Even pieces fitting in O(log n) by O(log n) boxes can encode hard jigsaw puzzles.

NP: completeness

Exact task

Can the supplied polyominoes exactly tile the square?

Scale & input

n finite grid-cell shapes and a square target whose area equals their total area.

Move rules

Orthogonal placements of all supplied pieces, without overlap.

Goal

Cover every target cell exactly once.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

A fixed catalog of shapes is a different restriction from the variable piece sets here.

Open this result in the map

Testing piece pairs gives a polynomial-time assembly method under this strong promise.

P: polynomial-time algorithm [atlas-derived]

Exact task

Can the puzzle be assembled when local fit identifies true neighbors?

Scale & rules

Explicit finite pieces. Every locally compatible pair is guaranteed to be adjacent in the final solution.

Scope

This is stronger than merely promising one global solution.

restriction: Promise that local compatibility identifies the true neighbor · Jigsaw · Fit every piece?. This comparison is not itself a reduction.

Open this result in the map

Hardness persists with at most four cells in every run.

NP: completeness

Exact task

Can the blank cells be filled with allowed digits so every horizontal and vertical run has its specified sum, without repeats in a run?

Scale & input

Variable grid; digits remain 1–9; each run has a sum.

Move rules

Digits cannot repeat within a horizontal or vertical run.

Goal

Satisfy all sums and distinctness constraints.

Repetition

Static assignment.

Players & information

One solver; all clues supplied.

Randomness

None.

Fixed digit alphabet, growing board. No uniqueness promise.

Open this result in the map

Even knowing the covered cards does not make every scalable deal easy.

NP: completeness

Exact task

Can a sequence of legal moves put every card of the supplied generalized Klondike deal onto the foundations?

Scale & input

Growing ranks and build stacks; three suits suffice.

Move rules

Alternating-color descending builds, ascending same-suit foundations; whole-block moves.

Goal

Move all cards to foundations.

Repetition

Finite successful certificate.

Players & information

One player; covered identities known.

Randomness

Deal supplied.

Specific no-stock/talon model; no return from foundations or empty-stack move. Not a claim about a fixed 52-card deck.

Open this result in the map

Fill the grid so every symbol appears once per row and column. Its completions can be embedded one-for-one in a larger Sudoku.

NP: completeness

Exact task

Decision: can a partial Latin square be completed?

Scale & input

An n×n grid using n symbols, with arbitrary givens.

Move rules

Fill blank cells; no sequential move restriction.

Goal

Every row and column has every symbol once, preserving givens.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Open this result in the map

One lemming is enough. Building and bashing let the player close and reopen passages.

PSPACE: completeness

Exact task

Can the single lemming be guided alive into an exit?

Scale & input

Explicit pixel landscape with steel and deadly zones. Skill budgets and allowed time can be exponentially large or unlimited.

Move rules

Only Builder and Basher skills; at most one skill assignment per time step.

Goal

Get the single lemming into an exit alive.

Repetition

Repeated paths and repeated construction/destruction allowed.

Players & information

One player; complete level and deterministic lemming behavior.

Randomness

None.

Not a polynomial-move-budget claim. The linked author manuscript is an earlier version whose main PSPACE theorem agrees with the 2015 final paper.

Open this result in the map

Polynomially many terrain-changing commands give a short certificate. Even with only Climber skills, choosing which lemmings to save encodes a satisfiability problem.

NP: completeness [atlas-derived]

Exact task

Can at least the required number of lemmings be rescued?

Scale & input

Explicit landscape. Builder, Basher and Miner budgets polynomial in landscape size. Other skill budgets may be larger. The total number of lemmings is polynomial in the number of landscape cells.

Move rules

All eight classic skills permitted under the given budgets. Deadly zones/traps are permitted. Other unavailable skills have budget zero in the hardness construction.

Goal

Rescue at least a supplied number of lemmings.

Repetition

Revisits and long waits allowed.

Players & information

One player; full deterministic level.

Randomness

None.

This concerns saving at least a supplied threshold of lemmings. It does not claim hardness for rescuing every lemming or for one lemming under these bounded budgets.

Open this result in the map

The paper asks whether removing deadly zones makes unlimited-skill rescue easier. Its PSPACE-hard construction uses such zones, and does not settle this restriction.

Open question in 2015 source

Exact task

Decide whether the single lemming can reach an exit.

Scale & input

Explicit scalable pixel landscape, one lemming, unlimited time and all skill types available without a usage bound.

Move rules

Original modeled skills and terrain rules. Remove deadly-zone objects, including traps and water. Long falls can still kill.

Goal

Save the one lemming.

Repetition

Revisits and terrain changes allowed.

Players & information

One solver, complete information.

Randomness

None.

Open in the cited 2015 source; later status is not established by this record. NP-hardness with limited skills does not classify levels where all skills are unlimited.

Open this result in the map

Press order does not matter. A linear system records whether each light is pressed an odd or even number of times.

P: polynomial-time algorithm

Exact task

Can presses transform the supplied initial pattern into the supplied target pattern?

Scale & input

Explicit finite undirected graph, including scalable rectangular grids, with initial and target bit patterns.

Move rules

A press toggles its vertex and all neighbors.

Goal

Reach the target pattern.

Repetition

Repeated presses allowed. Two presses at one vertex cancel.

Players & information

One player. Graph and both patterns known.

Randomness

None.

This P result is unrestricted reachability, not minimum presses on every graph family.

Open this result in the map

The matrix changes from A+I to A. Gaussian elimination still decides reachability.

P: polynomial-time algorithm

Exact task

Decide whether the target pattern is reachable.

Scale & input

Explicit arbitrary simple undirected graph and initial/target patterns.

Move rules

Press toggles neighbors only.

Goal

Reach target.

Repetition

Repeated presses allowed, parity suffices.

Players & information

One player. Complete input known.

Randomness

None.

rule change: Lights Out · Can the target light pattern be reached?. This comparison is not itself a reduction.

Open this result in the map

A short-solution requirement changes the neighbors-only graph problem from P to NP-complete.

NP: completeness

Exact task

Can the target be reached with at most w pressed vertices?

Scale & input

Explicit arbitrary simple undirected graph, initial/target bit patterns and integer w.

Move rules

Press toggles neighbors only.

Goal

Reach target with at most w presses.

Repetition

Repeated presses may be canceled in pairs.

Players & information

One player. Complete input known.

Randomness

None.

The hardness is for arbitrary graphs, not specifically ordinary rectangular self-toggling boards.

task change: Toggle neighbors but not the pressed light. This comparison is not itself a reduction.

Open this result in the map

A forced game encodes a Turing machine and wins exactly when the machine halts.

Undecidable: undecidability

Exact task

Will the designated player win this forced endgame?

Scale & input

A finite described reachable game state, using the paper’s card pool and rules. Standard-sized decks suffice, while counters and generated tokens have no fixed cap.

Move rules

All remaining actions are forced. Tokens, triggered effects and counters simulate a tape and transition rules. Numeric choices use binary notation.

Goal

Reach the designated player’s winning effect.

Repetition

Nonhalting simulation yields an unavoidable infinite loop, treated as a draw by the cited rule.

Players & information

Two players, no remaining strategic choices and no relevant hidden information.

Randomness

No stochasticity is used in the construction.

This does not model finite physical memory or tournament clocks, and it freezes the paper’s rules/card text instead of asserting compatibility with every later rules update.

Open this result in the map

The 2020 preprint proves a stronger lower bound for strategic play.

Arithmetic truth: hardness / lower bound (Arithmetic-truth lower bound for strategic play in the frozen 2020 model. No matching arithmetic upper bound is claimed.)

Exact task

Does a player have a winning strategy?

Scale & rules

The paper’s Magic rules and unbounded tokens/counters. Binary numeric choices, full information, no randomness.

Task

Its mate-in-n target means reaching a forced winning endgame within n strategic moves, not resolving the full game within n turns.

rule change: Allow players to choose numbers before the simulation starts · Magic: The Gathering · Forced endgame outcome. This comparison is not itself a reduction.

Open this result in the map

The authors conjecture that the transition function is computable.

Open question in 2021 source

Exact task

Given a state and a legal move, is the next state computable?

Scope

All cards under the paper’s rules. Numerical choices must use binary notation. The input move is promised legal.

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Ask about one transition instead of the eventual outcome · Magic: The Gathering · Forced endgame outcome. This comparison is not itself a reduction.

Open this result in the map

The authors conjecture that general move legality is undecidable.

Open question in 2021 source

Exact task

Is legality decidable for every proposed Magic move?

Scope

The paper’s rules/card pool and binary number convention. This is broader than the separately studied blocking step.

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

task change: Check legality instead of the eventual winner · Magic: The Gathering · Forced endgame outcome. This comparison is not itself a reduction.

Open this result in the map

The lower bound is proved. The matching upper bound is Conjecture 3.

Open question in 2020 source

Exact task

Is winning-strategy existence Turing-equivalent to arithmetic truth?

Scope

Biderman’s strategic Magic model, full information and binary numeric choices, with the card pool/rules frozen as in the paper.

New card text could alter the conjecture. This is a dated research question, not an established upper bound.

task change: Classify strategic play more precisely · Magic: The Gathering · Forced endgame outcome. This comparison is not itself a reduction.

Open this result in the map

Hardness already occurs with isolated stacks only three tiles high.

NP: completeness

Exact task

Can all tiles in the supplied, fully revealed Mahjong-solitaire layout be removed in matching free pairs?

Scale & input

Unbounded tiles; four of each matching type.

Move rules

Remove two matching tiles that are uncovered and each have a free left or right side.

Goal

Empty the layout.

Repetition

Tiles only disappear.

Players & information

One player; peeking reveals every identity.

Randomness

Layout supplied.

Solitaire, not multiplayer Mahjong.

Open this result in the map

With exactly four tiles of each type, these layouts are always solvable.

P: polynomial-time algorithm

Exact task

Can all tiles be removed when the layout consists of isolated stacks at most two high, with four copies per type?

Scale & input

Growing layouts of isolated stacks of height at most two, with exactly four copies of every tile type.

Move rules

Remove two matching tiles that are uncovered and each have a free left or right side.

Goal

Remove everything.

Repetition

Monotone removal.

Players & information

One player; all identities known.

Randomness

None.

Four copies per type is essential to the stated always-solvable result.

Open this result in the map

The first player wins by 10 stones under the cited rules. This is a finite-board solution, not an asymptotic hardness classification.

Fixed: fixed-instance result

Exact task

What is the optimal score from the Kalah(6,4) opening?

Scale & input

Exactly six pits per player, initially four stones each, and two empty stores.

Move rules

Sow counterclockwise from an own nonempty pit. Include your store, skip the opponent's store, and do not skip the starting pit on later laps. Ending in your store gives another move. Ending in an empty own pit captures that stone and the opposite pit, even when the opposite pit is empty.

Goal

When either side empties, the other player collects remaining stones. Maximize final score difference.

Repetition

Positions cannot repeat under these rules.

Players & information

Two players with fully known pit counts.

Randomness

None.

This paper does not classify the scalable winner problem. The empty-opposite capture convention matters.

Open this result in the map

This scalable winner problem is in PSPACE when the stone counts are unary. Every play has polynomially many sowing choices. This is an upper bound, not a hardness or completeness claim.

PSPACE: upper bound / membership (Atlas-derived membership for unary stone counts. Polynomial-length play follows from the displayed potential argument.) [atlas-derived]

Exact task

From an explicitly supplied position, can the designated player force a strictly larger final store count?

Scale & input

An explicit board with m pits per player and two stores, a player to move, and nonnegative stone counts encoded in unary. The initial position may be arbitrary. Let S be the total number of stones, including stores.

Move rules

Choose a nonempty own pit and sow counterclockwise. Include your store, skip the opponent's store, and do not skip the source pit on later laps. A final stone in your store gives another choice. A final stone in an empty own pit captures that stone and the opposite pit, including when the opposite pit is empty.

Goal

When either side empties, collect the remaining stones into the other player's store. The designated player wins exactly when their final store is larger. A tie is not a win.

Repetition

No extra repetition restriction is required. The decreasing rank proved below bounds every play by mS(S+1)+S sowings.

Players & information

Two players with fully visible counts and deterministic optimal play. Consecutive moves by one player are allowed when the sowing ends in their store.

Randomness

None.

The citation supplies the rules, not a published PSPACE theorem. This bound does not prove PSPACE-hardness. The unary length assumption matters to this particular proof.

Open this result in the map

The cited ruleset was strongly solved: perfect play draws. This does not classify growing-board Awari or other Oware rules.

Fixed: fixed-instance result

Exact task

Determine optimal play on the fixed Awari board.

Scale & rules

Two rows of six pits, four stones each. Sow from an own pit counterclockwise, skipping the starting pit on a lap. A last stone making an enemy pit hold two or three captures it and consecutive preceding enemy pits with two or three.

Ending & repetition

Choose a move leaving the opponent a stone whenever possible. Otherwise a grand slam captures every opposing stone, and the mover also collects all remaining stones because the opponent cannot move. Repetition ends play and divides uncollected stones equally, allowing half-stones. The companion rules note specifies threefold repetition.

Players & goal

Two players, known counts, no randomness. Capture more than 24 of the 48 stones to win.

Traditional Oware capture and ending conventions differ.

rule change: Change capture, feeding and repetition rules · Kalah · Fixed 6×4 opening. This comparison is not itself a reduction.

Open this result in the map

A winning play must always use the nearest harvestable bin. This gives a polynomial-time solvability test.

P: polynomial-time algorithm [atlas-derived]

Exact task

Given a bin vector, can every stone reach the store?

Scale & rules

Input is an explicit vector of k nonnegative binary counts. Bin i is i steps from the store. Only a bin containing exactly i stones can be sown, depositing one in each earlier bin and finally the store.

Players & goal

One player, full information, no randomness. Empty all bins.

Repetition

Each move permanently stores one stone, so no repeated state.

P follows from the cited characterization: reject any count above its bin index, then simulate at most k(k+1)/2 forced moves. This is not a winner result for two-player Kalah.

rule change: Replace adversarial play with an all-sowings-end-in-store solitaire task · Kalah · Fixed 6×4 opening. This comparison is not itself a reduction.

Open this result in the map

The paper finds winning openings for Dakon-n at n=2 and 4 through 18, but none at n=3. These finite searches do not establish a complexity class.

Fixed: fixed-instance result

Exact task

Can the initial player capture enough stones during the first turn to prevent another round?

Scale & rules

Dakon-n has n pits per side, initially n stones per pit, and stores. Sow counterclockwise through your store, skipping the opponent's. If the last stone lands in a nonempty pit, pick that pit up and keep sowing. Ending in your store grants another choice. Ending in an empty own pit captures it and the opposite pit.

Ending & information

Two players, known counts, deterministic. Rounds refill pits with n stones each and skip unfillable pits. A player unable to fill one pit loses. This record concerns only the terminating first-turn construction, not general repetition behavior.

rule change: Add relay sowing and round-based refill rules · Kalah · Fixed 6×4 opening. This comparison is not itself a reduction.

Open this result in the map

Removing capture does not break the polynomial play-length bound. Ordinary sowing still permanently adds stones to stores, and all other sowings move stones closer to their own store.

PSPACE: upper bound / membership (Atlas-derived membership for unary stone counts. Polynomial-length play follows from the displayed potential argument.) [atlas-derived]

Exact task

Can the designated player force a larger final store count after removing the opposite-pit capture rule?

Scale & input

Explicitly list m pits per side, two stores, whose turn it is and unary stone counts. Arbitrary initial positions are allowed.

Rule change

Use the Kalah rules in the linked unary winner record but disable the last-stone/opposite-pit capture. Keep sowing into your own store, skipping the opponent's store, bonus choices for a last stone in your store, and final collection when one side empties.

Players & goal

Two players, fully visible counts, no randomness. Finish with strictly more stored stones than the opponent. A tie is not a win.

Repetition

No repetition rule is needed: the same rank R=(S−C)(mS+1)+Φ strictly decreases.

The polynomial-space result establishes membership only, not PSPACE-hardness or completeness.

rule change: Disable the opposite-pit capture · Kalah · Scalable board, unary counts. This comparison is not itself a reduction.

Open this result in the map

Binary notation can describe exponentially many stones. A finite-state search gives an EXPTIME upper bound. This weaker bound does not show that binary Kalah is harder or rule out PSPACE.

EXPTIME: upper bound / membership (Atlas-derived exponential-time membership for binary stone counts. Polynomial-size states alone do not prove PSPACE membership.) [atlas-derived]

Exact task

Decide the same winner problem when each pit count is written in binary.

Scale & input

The m-pit rows are explicitly listed. All pit and store counts are nonnegative binary integers, with their total S. The player to move and designated player are specified.

Move rules

Identical to the unary Kalah winner record, including captures, bonus choices, no source-pit skip and final collection. Only the encoding changes.

Players & goal

Two players, fully visible counts, deterministic play. The designated player must finish with a strictly larger store.

Repetition

The same decreasing rank guarantees termination, but its mS(S+1)+S bound is not polynomial in binary input length.

A polynomial-size position by itself does not imply a polynomial-space winner algorithm. No EXPTIME-hardness, separation from unary Kalah, or optimality of this upper bound is claimed.

encoding change: Write stone counts in binary · Kalah · Scalable board, unary counts. This comparison is not itself a reduction.

Open this result in the map

Consistency is hard even with only two colors.

NP: completeness

Exact task

Does at least one secret code produce every supplied guess rating?

Scale & input

Code length and explicit guess list grow. Two colors already suffice.

Move rules

Feedback gives correct positions and correct colors in wrong positions. Repeated colors allowed.

Goal

Find whether a compatible code exists.

Repetition

Static completion, no play-history restriction.

Players & information

Offline consistency problem. Guesses and ratings known, code hidden.

Randomness

None.

Not optimal adaptive codebreaking. In a truthful live game, consistency is already promised.

Open this result in the map

Counting remains hard with just two colors.

#P: completeness (Counting consistent secrets. A #P result, not winner determination or mere existence.)

Exact task

Count secret codes consistent with the supplied ratings.

Scale & input

Growing code length and explicit query list. Two colors suffice.

Move rules

Usual black and white feedback, repeated colors allowed.

Goal

Count compatible ordered codes.

Repetition

Static completion, no play-history restriction.

Players & information

Offline list known, hidden code not given.

Randomness

None.

task change: Mastermind · Do the guesses fit any code?. This comparison is not itself a reduction.

Open this result in the map

Removing misplaced-color feedback leaves two-color consistency hard.

NP: completeness

Exact task

Decide whether supplied guesses and exact-position counts have a compatible code.

Scale & input

Growing length and query list. Two colors suffice.

Move rules

Feedback counts matching positions only.

Goal

A compatible ordered code exists.

Repetition

Static completion, no play-history restriction.

Players & information

Offline queries and ratings known.

Randomness

None.

rule change: Mastermind · Do the guesses fit any code?. This comparison is not itself a reduction.

Open this result in the map

A fixed palette gives only polynomially many color-count vectors to check.

P: polynomial-time algorithm

Exact task

Count compatible unordered codes.

Scale & input

Growing code length, constant number of colors, explicit query list.

Move rules

Feedback counts color matches ignoring position, including exact-position matches.

Goal

Count compatible color multisets.

Repetition

Static completion, no play-history restriction.

Players & information

Offline queries and ratings known.

Randomness

None.

The paper’s white-only score is total color overlap, not ordinary white feedback alone.

rule change: Mastermind · Do the guesses fit any code?. This comparison is not itself a reduction.

Open this result in the map

Samus can clear a route earlier by shooting enemies from a different corridor. Later, Morph Ball mode removes the option to shoot.

NP: hardness / lower bound · PSPACE: upper bound / membership (Membership applies to the source’s finite-state game model and stated encoding assumptions.)

Exact task

Can the player reach the specified target location?

Scale & input

Explicit arbitrary-size map with polynomial-bit room and object state and enough persistent state for the gadgets.

Move rules

Original Metroid movement and shooting; Morph Ball and Zoomers.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; full level and modeled engine state.

Randomness

Deterministic engine once its polynomial-bit pseudorandom state is supplied. The hardness construction succeeds independently of favorable health drops.

The upper bound is for the deterministic modeled engine, including a supplied polynomial-bit pseudorandom state. It is not an almost-sure-win or expected-score theorem for hidden genuine randomness.

Open this result in the map

Check whether any placement of mines fits the revealed numbers.

NP: completeness

Exact task

Does any placement of mines satisfy every revealed number on the supplied board?

Scale & input

Variable rectangular grid; partial clues.

Move rules

Clues count eight neighboring cells.

Goal

Some consistent mine placement exists.

Repetition

Static assignment.

Players & information

One reasoner; clues visible, mines unknown.

Randomness

None.

Not the problem of choosing a safe click.

Open this result in the map

A safe deduction must hold for every mine placement compatible with the clues.

coNP: completeness

Exact task

Is there a covered cell that is safe in every mine placement consistent with the revealed clues?

Scale & input

Variable rectangular partial board. Consistency of the revealed clues is not promised.

Move rules

Same eight-neighbor clues.

Goal

Some covered cell is safe in every completion.

Repetition

One deduction, no repeated play.

Players & information

Hidden mines; visible clues.

Randomness

No probabilities assumed.

If clues are inconsistent, every covered cell satisfies the universal safety condition vacuously: there are no fitting mine placements. The formal decision problem therefore differs from restricting input to consistent live-game boards. Uses the repaired 2024 inference proof.

Open this result in the map

This is stronger than displaying only 2s among the visible clues. Unrevealed safe cells must also become 2s. The thesis leaves this case unclassified.

NP: upper bound / membership · Open question in 2018 source

Exact task

Decide consistency when every nonmine cell in the completed board must have exactly two adjacent mines.

Scale & input

Explicit finite rectangular partial board, with eight-neighbor clues.

Move rules

Complete unknown cells with mines or safe cells, respecting the visible entries and the all-2 rule.

Goal

Existence of a legal completion.

Repetition

Not a move-sequence task.

Players & information

One solver sees the entire partial instance.

Randomness

None.

Dated question. The 2024 Minesweeper-variants paper concerns other rules and does not supply a resolution for this completed-board restriction.

rule change: Require all safe cells, revealed or hidden, to have clue 2 · Minesweeper · Can the clues all be true?. This comparison is not itself a reduction.

Open this result in the map

Compute the bitwise XOR of the heap sizes. A nonzero result means a winning move exists. This takes polynomial time for binary or unary input.

P: polynomial-time algorithm

Exact task

Decision: does the player to move have a winning strategy?

Scale & input

A scalable explicit list of heap sizes, in binary or unary. A binary heap h uses O(log(h+1)) bits, but the input also includes every heap.

Move rules

Remove any positive number of counters from one heap.

Goal

Take the last counter.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The XOR algorithm makes Nim easy. Compact binary notation alone does not imply efficient solvability, and changing to unary does not make ordinary Nim hard.

Open this result in the map

The same XOR test works until every nonempty heap has size one. Then parity decides the outcome.

P: polynomial-time algorithm

Exact task

Decision: does the player to move have a winning strategy?

Scale & input

A scalable explicit list of heap sizes, in binary or unary.

Move rules

Remove any positive number from one heap.

Goal

Make the opponent take the last counter.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

With only singleton heaps remaining, an even positive number of heaps is winning.

Open this result in the map

Heaps are 0/1. For direct equivalence with undirected vertex Geography, the previous-move vertex starts empty. Winner determination is polynomial-time.

P: polynomial-time algorithm

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every move strictly decreases one heap. No pass is permitted and no full state repeats.

Randomness

None.

equivalence: Geography · Two-way · no vertex reuse.

Open this result in the map

Heaps are 0/1/2. PSPACE-complete by directed Geography reduction. Each arc becomes a seven-vertex internal gadget with one heap of 2, all others 1.

PSPACE: completeness

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every move strictly decreases one heap. No pass is permitted and no full state repeats.

Randomness

None.

rule change: Allow heaps of size 2 · Neighboring Nim: heaps of at most 1. This comparison is not itself a reduction.

Open this result in the map

Arbitrary binary heaps preserve PSPACE-hardness. An exponential-time upper bound follows by evaluating all positions. Whether this can be improved to polynomial space is Open Problem 6.1 in the 2017 source.

PSPACE: hardness / lower bound · EXPTIME: upper bound / membership (Atlas-derived finite-state exponential-time upper bound under this record’s explicit rules.) [atlas-derived] · Open question in 2017 source

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every move strictly decreases one heap. No pass is permitted and no full state repeats.

Randomness

None.

PSPACE membership was open in the 2017 source; later status is not established by this record. The EXPTIME upper bound is derived from its rules, not claimed as a named theorem in that paper.

restriction: Bound every heap by 2 · Neighboring Nim: heaps of at most 2. This comparison is not itself a reduction.

Open this result in the map

Exactly three heaps and one shared pass, unavailable after all heaps empty. A May 2026 primary source still identifies the general losing-position formula as open. This does not establish PSPACE-hardness.

Open question in 2026 source

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input: binary heap sizes and whether a shared pass is unused. Make a normal Nim move or an allowed pass. A pass is consumed globally.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every move decreases a heap or uses the single pass. No repeated state.

Randomness

None.

This is an open characterization question in the May 2026 cited source. It is not itself a complexity lower bound.

rule change: Add one nonterminal pass · Nim · Take the last counter. This comparison is not itself a reduction.

Open this result in the map

Changing pass availability restores a polynomial-time XOR test. XOR all heaps with a bit that is 1 exactly when a pass is unused and some heap is at least 2. Otherwise that bit is 0.

P: polynomial-time algorithm

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input: binary heap sizes and whether a shared pass is unused. Make a normal Nim move or an allowed pass. A pass is consumed globally.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every move decreases a heap or uses the single pass. No repeated state.

Randomness

None.

rule change: Pass threshold changes from 1 to 2 · Three-pile Nim with one shared pass. This comparison is not itself a reduction.

Open this result in the map

Explicit 0/1 matrix: rows are configurations, columns are heaps. Only single ordinary moves are permitted, with illegal rows discarded. PSPACE-complete and polynomially isomorphic to Avoid True: each row maps to a clause on its zero columns.

PSPACE: completeness

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Explicit scalable 0/1 matrix. Rows are alternative positions on named heaps. Choose one heap, remove its stick from each legal row, discard illegal rows. No superposed moves.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Each move removes one counter in every surviving row and discards rows where that move is illegal. No pass is allowed.

Randomness

None. Alternative configurations are deterministic, not random measurements.

equivalence: Avoid True.

Open this result in the map

Explicit polynomial-width list of 0/1 heap configurations. Proved Σ₂^P-hard, and in PSPACE by Theorem 7.1. Completeness is unresolved in the source. The rule change allows superposed moves.

Σ₂^P: hardness / lower bound · PSPACE: upper bound / membership

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input configurations share named heaps. Flavor D, width 2: select one ordinary move or two alternative moves, each legal somewhere. Retain every legal successor branch. This is deterministic, not probabilistic quantum mechanics.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every surviving branch removes one counter per turn. No pass is allowed.

Randomness

None. Superposed moves are deterministic branching rules.

rule change: Allow superpositions of moves · Demi-quantum Boolean Nim. This comparison is not itself a reduction.

Open this result in the map

Single ordinary starting configuration, scalable heaps of size 0/1/2. In PSPACE. Open Question 8.3 asks whether it is polynomial-time solvable or PSPACE-complete, without asserting either.

PSPACE: upper bound / membership · Open question in 2020 source

Exact task

Decide whether the next player wins under optimal play.

Scale & input rules

Input configurations share named heaps. Flavor D, width 2: select one ordinary move or two alternative moves, each legal somewhere. Retain every legal successor branch. This is deterministic, not probabilistic quantum mechanics.

Players & information

Two alternating players, complete information.

Goal

The player with no legal move loses.

Repetition

Every surviving branch strictly loses counters each turn. No pass is allowed.

Randomness

None. Superposed moves are deterministic branching rules.

Open question in the cited 2020 source. Later status is not established by this record.

rule change: Different starting-position promise, not a reduction · Quantum Boolean Nim from a superposition. This comparison is not itself a reduction.

Open this result in the map

An ordinary starting position is easy by parity. A supplied superposition of such positions has a proved hardness lower bound.

P: polynomial-time algorithm

Exact task

Determine the winner from one ordinary 0/1-heap position.

Scale & rules

Scalable list of heaps, each 0 or 1. Flavor D, width 2: choose one ordinary move or two alternatives, each legal somewhere. Retain legal successor branches.

Players & goal

Two alternating players, perfect information. The player with no legal move loses.

Repetition & randomness

Each branch removes a stick per turn. No repeated positions or randomness. These are deterministic quantum-inspired rules.

restriction: Start with one ordinary position instead of a supplied superposition · Quantum Boolean Nim from a superposition. This comparison is not itself a reduction.

Open this result in the map

A subtraction size can be used only once across all piles. With S explicitly listed, at most |S| moves remain. Depth-first game-tree evaluation uses polynomial space, for binary or unary integers.

PSPACE: upper bound / membership (Atlas-derived polynomial-space bound for an explicitly listed move set S, in unary or binary; excludes a succinct unexpanded interval.) [atlas-derived]

Exact task

Determine whether the player to move can win from supplied piles and available subtraction sizes.

Scale & input

An explicit list of nonnegative pile sizes and a finite explicit set S of positive integers. Pile count and |S| scale. Values may be binary or unary.

Move rules

Choose s in S and one pile containing at least s counters. Subtract s from that pile and delete s from S globally.

Goal

Normal play: the player with no legal move loses.

Repetition

No move size is reused. Every turn reduces |S| by one.

Players & information

Two alternating players, with all piles and S visible.

Randomness

None.

This record establishes PSPACE membership only, without a matching lower bound or polynomial-time algorithm. The bound does not cover a succinct interval S={1,...,M} when M is binary and the interval is not expanded.

rule change: Supply allowed move sizes and forbid their reuse globally · Nim · Take the last counter. This comparison is not itself a reduction.

Open this result in the map

Theorem 7.1 gives PSPACE membership. Open Question 8.3 asks whether this problem has a polynomial-time algorithm or is PSPACE-complete. Ordinary unary Nim still has the XOR solution.

PSPACE: upper bound / membership · Open question in 2020 source

Exact task

Determine the winner from one ordinary position with unary-encoded heaps under the specified quantum-inspired rules.

Scale & input

A scalable explicit list of heaps, with every heap size written in unary. The initial position is one ordinary configuration, not a supplied superposition.

Move rules

Flavor D, width 2: choose one ordinary Nim move or two alternative Nim moves, each legal in some current branch. Retain all legal successor branches.

Goal

Normal play: the player with no legal move loses.

Repetition

Every surviving branch decreases its counter total. The maximum play length is at most the initial unary counter total.

Players & information

Two alternating players. The initial position and all choices are public.

Randomness

None. The branching rules are deterministic and do not model random measurements.

The cited 2020 source poses P versus PSPACE-complete as an open question, not a proved dichotomy. Later status is not established by this record.

restriction: Restrict each unary heap to 0, 1 or 2 · Quantum Nim: heaps of at most 2, ordinary start. This comparison is not itself a reduction.

Open this result in the map

Row and column clues jointly constrain a hidden picture.

NP: completeness

Exact task

Does a black-and-white grid exist with exactly the supplied runs in every row and column?

Scale & input

Variable m × n grid and run-length clues.

Move rules

Fill cells black or white.

Goal

Every ordered run-length list matches.

Repetition

Static assignment.

Players & information

One solver; all clues given.

Randomness

None.

No uniqueness promise.

Open this result in the map

Island sizes and a connected black region jointly impose hard constraints.

NP: completeness

Exact task

Can the supplied clues be completed to islands of the required sizes, separated by one connected sea with no 2×2 sea block?

Scale & input

Growing numbered rectangular grid.

Move rules

White components each contain one clue equal to their size; black cells connected, with no black 2 × 2 block.

Goal

Complete the black/white coloring.

Repetition

Static assignment.

Players & information

One solver; visible clues.

Randomness

None.

Evidence is limited to the publisher abstract. This record does not include a construction sketch.

Open this result in the map

Tiny islands do not make the general problem easy.

NP: completeness

Exact task

Does the same island-and-sea puzzle have a solution when every numerical clue is 1 or 2?

Scale & input

Same grid, with all clues restricted to 1 or 2.

Move rules

Same island and sea conditions.

Goal

Complete the coloring.

Repetition

Static.

Players & information

Complete clues.

Randomness

None.

Evidence is limited to the publisher abstract; no full-text proof is linked.

Open this result in the map

Flipping disks can simulate a route through a graph. A final region makes the simulated result decide the score.

PSPACE: completeness

Exact task

Decision: can Black force a win from this position?

Scale & input

Arbitrary position on a variable n×n board.

Move rules

Place a disk bracketing opposing disks; flip all bracketed lines. Pass only without a legal move.

Goal

More disks after both players pass.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The result concerns arbitrary growing boards, not the usual opening on 8×8.

Open this result in the map

Planning is NP-complete on scalable maps even with one player.

NP: completeness

Exact task

Can the team find every cure before losing?

Scale & input

An explicit city graph, player positions, hands, infections, and all future player/infection draws, including reshuffles.

Move rules

Four actions per turn: movement/flights, build, share, cure, or treat. Seven-card hand limit. Cure uses five matching-color city cards at a lab. Draw two player cards per turn.

Goal

Find all cures before eight outbreaks or player-deck exhaustion.

Repetition

At most |V|/2+3 turns under the specified deck rules.

Players & information

Cooperative players, with all future card outcomes supplied.

Randomness

Draw and reshuffle outcomes are fixed input.

Does not classify optimal play with genuinely unknown future draws.

Open this result in the map

Removing pegs can simulate a planar logic circuit.

NP: completeness

Exact task

Can legal peg jumps leave exactly one peg at the specified target position?

Scale & input

n × n board, initial pegs and a target hole; n grows.

Move rules

Jump orthogonally over an adjacent peg into an empty hole; remove jumped peg.

Goal

Exactly one peg remains at the designated hole.

Repetition

Every move removes a peg.

Players & information

One player; full board known.

Randomness

None.

Arbitrary generalized configurations; not just the standard 33-hole opening.

Open this result in the map

Battles can be predetermined wins or losses and route planning is still hard. A trainer who steps forward changes which corridors are safe.

NP: completeness

Exact task

Can the player reach the target through the supplied trainer layout?

Scale & input

Arbitrary-size overworld; fixed-size Pokémon teams and battle mechanics.

Move rules

Walls and enemy trainers only in the overworld. Trainers have sight lines, approach the player and become inert after defeat.

Goal

Reach a target location by a successful route.

Repetition

Travel may revisit squares. Each trainer battle changes that trainer permanently.

Players & information

One human player; trainer layouts and battle states given. Battle subgames have constant size in the model.

Randomness

Hardness uses battles with certain outcomes. No hidden team information or random encounter mechanic is used.

This is not competitive Pokémon battle complexity. Restricting the overworld to trainers is essential to the NP upper bound.

Open this result in the map

Portals are not needed: a cube placed on either of two floor buttons stores a bit that controls doors elsewhere.

PSPACE: completeness

Exact task

Can the player reach the exit in the cube-and-door model?

Scale & input

Arbitrary-size discretized 3D level; fixed-point positions/velocities and polynomially described state.

Move rules

Pick up cubes, press weighted buttons, pass connected doors. No Portal Gun or long-fall mechanic required.

Goal

Reach the level exit.

Repetition

Backtracking and repeated switch changes allowed.

Players & information

One player; complete level.

Randomness

None in the construction.

The result concerns the specified generalized finite-state model, not the finite set of shipped test chambers.

Open this result in the map

The exit opens only while every timer is active. Reaching it becomes a race to visit every switch without wasting a detour.

NP: hardness / lower bound · PSPACE: upper bound / membership (Membership applies to the source’s finite-state game model and stated encoding assumptions.)

Exact task

Can the player reach the exit while the required timed doors are open?

Scale & input

Explicit arbitrary-size level with configurable timer lengths. Polynomial-bit finite-precision state and polynomially bounded velocities, as in Theorem 12.

Move rules

Walk between timed buttons; buttons temporarily open connected doors. No Portal Gun needed.

Goal

Reach the exit before required doors close.

Repetition

Revisits allowed, but timers can make them fatal to a successful route.

Players & information

One player; full level and timer settings.

Randomness

None in the construction.

Configurable timers are required for hardness. PSPACE membership assumes the paper's finite-precision model, polynomially bounded velocities and polynomial-bit state. This does not assert NP-completeness.

Open this result in the map

Laser-controlled platforms implement reusable memory latches.

PSPACE: completeness

Exact task

Decide whether the player can reach the exit.

Scale & input

Growing discretized 3D level, polynomially described finite state.

Move rules

Portals redirect lasers. Relays control moving platforms.

Goal

Reach the exit.

Repetition

Backtracking and repeated latch changes allowed.

Players & information

One player. Entire level known.

Randomness

None.

rule change: Portal · Cubes, floor buttons and doors. This comparison is not itself a reduction.

Open this result in the map

Activating every catcher within the constructed timing constraint encodes a grid Hamiltonian cycle.

NP: hardness / lower bound · PSPACE: upper bound / membership (Atlas-derived membership for the stated finite-precision, polynomial-bit engine model.) [atlas-derived]

Exact task

Decide whether the player can reach the exit.

Scale & input

Explicit growing level with pellet launchers, catchers, portals and catcher-controlled doors. Positions, velocities and timer states have polynomial-bit finite-precision encodings. Velocities are polynomially bounded, as assumed by the paper's PSPACE argument.

Move rules

Redirect pellets through portals. Pellets reflect and can kill the player. A launcher replaces its pellet only after the prior pellet is destroyed, so the number of active pellets remains bounded by the input.

Goal

Reach exit.

Repetition

Revisits allowed, timing can prevent a successful detour.

Players & information

One player. Entire level known.

Randomness

None.

NP-hardness is a published theorem. The PSPACE upper bound applies to the specified finite-precision engine with polynomially bounded velocities and polynomial-bit state. It is not a claim about exact real-valued physics or NP-completeness.

rule change: Portal · Cubes, floor buttons and doors. This comparison is not itself a reduction.

Open this result in the map

The authors explicitly leave the portals-only mechanics set unresolved.

Open question in 2018 source

Exact task

Reach an exit using only portal placement and ordinary movement.

Scale & input

Scalable polygonal level with fixed-point coordinates and discrete time.

Move rules

One portal pair, ordinary movement, no other puzzle devices.

Goal

Reach the target.

Repetition

Allowed.

Players & information

One player, complete information.

Randomness

None.

Open in the cited 2018 source. Later status is not established by this record.

Open this result in the map

Cubes alone are an explicit open mechanics set. The proved cube result also uses buttons and doors.

Open question in 2018 source

Exact task

Reach an exit using movable cubes and ordinary movement.

Scale & input

Scalable polygonal level, discrete fixed-point model.

Move rules

Carry cubes and use them as platforms. No other puzzle devices.

Goal

Reach the target.

Repetition

Allowed.

Players & information

One player, complete information.

Randomness

None.

Open in the cited 2018 source. Later status is not established by this record.

restriction: Remove buttons and doors · Portal · Cubes, floor buttons and doors. This comparison is not itself a reduction.

Open this result in the map

Wall placement can encode a formula. Having a path available does not mean you can win the race.

PSPACE: completeness

Exact task

Decision: can White force a win from a supplied position?

Scale & input

n×n board, one pawn each; existing walls and remaining wall supplies are input. Wall supply grows with board area.

Move rules

Move the pawn, including a jump over an adjacent opposing pawn or a side-step when a straight jump is blocked, or place a length-two wall. Walls cannot cross or overlap. Each player must retain a path to a goal edge.

Goal

Reach the opposite edge first.

Repetition

No repetition ban or move cap. Endless play is not a forced win.

Players & information

Two opponents; complete information.

Randomness

None.

Publication status

2026 preprint. The linked manuscript supplies the stated result.

2026 preprint result for supplied positions, not a solution of the standard 9×9 opening.

Open this result in the map

A scalable, legally scrambled cube can be solved efficiently if the solution need not be shortest.

P: polynomial-time algorithm (Polynomial-time search under the exact input and move rules of this record.)

Exact task

Find a sequence of legal turns that solves the supplied reachable, generalized Rubik’s Cube configuration.

Scale & input

n × n × n cube, n grows; legal scramble promised.

Move rules

Rotate individual slices.

Goal

Restore solved face colors.

Repetition

Turns may be undone; no repetition ban.

Players & information

One player; all stickers known.

Randomness

None.

This is a search guarantee on valid scrambles, not a decision about arbitrary sticker colorings.

Open this result in the map

Requiring the shortest route makes a different computational problem.

NP: completeness

Exact task

Can the supplied generalized Rubik’s Cube configuration be solved in at most the given number k of turns?

Scale & input

Variable n × n × n cube plus k.

Move rules

One slice per move; slice-turn or slice-quarter-turn metric.

Goal

Reach solved colors using at most k moves.

Repetition

Revisits allowed.

Players & information

One player; complete configuration known.

Randomness

None.

Not the fixed 3 × 3 × 3 cube, and not whole-cube rotations as free slice moves.

Open this result in the map

Fixing two dimensions permits optimal solving in polynomial time.

P: polynomial-time algorithm (Polynomial-time search under the exact input and move rules of this record.)

Exact task

Find a shortest solving sequence.

Scale & input

c1×c2×n cuboid. c1 and c2 are constants, n grows. Reachable configuration.

Move rules

Legal slice turns preserving the cuboid, under the paper’s move model.

Goal

Minimize number of turns to solve.

Repetition

Reversible turns, revisits allowed.

Players & information

One player. All sticker colors known.

Randomness

None.

restriction: Rubik's Cube · Can it be solved within k turns?. This comparison is not itself a reduction.

Open this result in the map

The shortest-solution theorem covers one slice at a time. The authors ask what happens when one move rotates a contiguous bundle of layers touching a face.

Open question in 2018 source

Exact task

Decide whether a scalable n × n × n cube can be solved within k wide turns.

Scale & input

Growing cube, explicit sticker configuration and move budget k.

Move rules

WTM permits quarter or half turns of a face-adjacent bundle. WQTM counts only quarter turns.

Goal

Make faces monochromatic within k moves.

Repetition

Repeated states allowed, subject to the budget.

Players & information

One solver, complete information.

Randomness

None.

Open in the cited 2018 source. Later status is not established by this record.

rule change: Count a wide turn as one move · Rubik's Cube · Can it be solved within k turns?. This comparison is not itself a reduction.

Open this result in the map

Even with only straight cars of length two or three, deciding whether the exit car can escape is PSPACE-complete on growing boards.

PSPACE: completeness

Exact task

Decision: can a designated car reach its exit?

Scale & input

A growing grid with 1×2 and 1×3 cars.

Move rules

Cars translate only along their long axis; no turning or overlapping.

Goal

Bring the designated car to the specified border location.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Open this result in the map

Even single-cell cars can encode long dependencies.

PSPACE: completeness

Exact task

Can the designated car reach the left boundary?

Model & rules

Growing explicit n × n board, one empty cell. Each unit car moves only horizontally or only vertically. Some cells are fixed obstacles. One player, full information, no randomness. Revisiting positions is allowed.

Open this result in the map

Removing fixed obstacles was left unresolved by the unit-car hardness paper.

Open question in 2020 source

Exact task

Can the designated unit car reach the left boundary?

Model & rules

Growing explicit square grid. Every car is movable but retains its horizontal or vertical direction. No fixed obstacles. One player, full information, no randomness, repeated positions allowed.

This is a dated open question, not an assertion that no later solution exists.

rule change: Permit fixed obstacles · Single-cell cars and fixed obstacles. This comparison is not itself a reduction.

Open this result in the map

The result survives constant alphabet, dictionary and rack size in a derandomized model.

PSPACE: completeness

Exact task

Decision: can the designated player force a higher final score?

Scale & input

Growing n×n board, tile bag and given position. Alphabet, dictionary and rack size can be fixed constants for the two-player theorem.

Move rules

Place connected dictionary words horizontally or vertically. All letters score 1, no premium squares. Refill from the known bag order. No exchanges or passes in this model.

Goal

Higher score when the bag empties or the next player cannot form a legal word.

Repetition

Placed tiles never move or disappear.

Players & information

Two alternating players. Both racks and the entire bag order are known.

Randomness

None. The bag order is input.

Not a theorem about the fixed English-language commercial game or hidden random tile draws.

Open this result in the map

Removing the opponent gives the NP-complete solitaire placement task.

NP: completeness

Exact task

Decision: can one player place every tile?

Scale & input

Growing n×n board and explicit tile sequence, dictionary, alphabet and rack size. Lemma 1 permits these parameters to grow.

Move rules

Place connected dictionary words horizontally or vertically. All letters score 1, no premium squares. Refill from the known bag order. No exchanges or passes in this model.

Goal

Place every tile.

Repetition

Placed tiles never move or disappear.

Players & information

One player, full board and tile order known.

Randomness

None. The bag order is input.

The result concerns a growing explicit input family, not a fixed commercial set.

Open this result in the map

A constant total tile count leaves only polynomially many configurations as the board grows.

P: polynomial-time algorithm

Exact task

Determine the winner in the derandomized model.

Model & rules

Growing explicit board, constant total tiles including the position and bag, known bag order and racks. Two players, equal letter scores, no random draws, tiles never removed.

The constant is the total number of tiles in the instance, not merely the tiles left in a small bag beside an arbitrarily populated board.

restriction: Bound total tile count · Scrabble · Known bag order. This comparison is not itself a reduction.

Open this result in the map

If you only ask whether a solution exists, the scalable sliding-tile puzzle has a polynomial-time algorithm. The challenge changes when the route must be short.

P: polynomial-time algorithm

Exact task

Decision: does any sequence reach the target arrangement?

Scale & input

An n×n board with n²−1 distinct unit tiles and one blank; both arrangements are input.

Move rules

Swap the blank with an orthogonally adjacent tile, one tile per move.

Goal

Reach the complete prescribed arrangement.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Open this result in the map

The same tiles become an NP-complete decision problem when you must reach the target within a specified number of slides.

NP: completeness

Exact task

Decision: reach the target in at most input k single-tile moves.

Scale & input

Same n×n, n²−1 distinct tiles and one blank; start, target and k are input. The nonnegative integer k may be binary encoded; polynomial puzzle diameter bounds a needed certificate.

Move rules

A single adjacent tile slides into the blank; this costs one move.

Goal

Reach target without exceeding k.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Finding a shortest sequence is an optimization problem and NP-hard; the label here is for its budget decision version.

Open this result in the map

A single loop can encode a tour that visits every graph vertex.

NP: completeness

Exact task

Can a single loop be drawn along grid edges so each numbered cell has exactly that many loop edges on its boundary?

Scale & input

Variable rectangular dot lattice; cells may have clues 0–3.

Move rules

Choose edges between neighboring dots; no branching or crossing.

Goal

One loop, with each clue counting its incident boundary edges.

Repetition

Static edge selection.

Players & information

One solver; every clue known.

Randomness

None.

No uniqueness promise.

Open this result in the map

Pushing crates is powerful enough to simulate a constraint graph. Hardness even survives removing fixed barrier pieces from the scalable puzzle.

PSPACE: completeness

Exact task

Decision: can every target square be occupied by a crate?

Scale & input

Growing finite grid with a walker, unit crates and an equal number of target cells. This record uses the no-fixed-barrier construction.

Move rules

Walker moves one orthogonal step, pushing at most one crate if the next cell is empty; pulling prohibited.

Goal

Crates occupy all targets.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

No fixed barriers does not mean no obstacles: packed crates can be immovable. Reduction starts from NCL configuration-to-configuration, not directly the edge task.

Open this result in the map

Replacing crate-storage goals with one player destination still leaves a PSPACE-complete problem.

PSPACE: completeness

Exact task

Push-1F: can the player reach a designated cell?

Model & rules

Growing explicit rectangular grid with unit crates and fixed walls. Orthogonal steps may push one crate by one cell into empty space. No pulling or gravity. One player, full information, no randomness. Positions may repeat.

A related rule-and-goal variant called Push-1F, not the ordinary Sokoban storage task.

rule change: Remove internal fixed walls · Reach an exit without fixed walls. This comparison is not itself a reduction.

Open this result in the map

The no-fixed-wall reachability question was settled by a 2025 proof, revised in 2026.

PSPACE: completeness

Exact task

Push-1: can the player reach the specified destination?

Model & rules

Growing explicit rectangular grid, unit movable crates, start and destination. Orthogonal moves push at most one crate one cell. No pulling, gravity or internal fixed walls. Repeated positions allowed. One player, complete information, no randomness.

Clusters of movable crates can still be immobile. Older sources that list this task as open are outdated.

Open this result in the map

The paper proves hardness for a storage-goal uniqueness promise, then conjectures analogous hardness when the objective is reaching an exit. Ordinary walks between pushes do not distinguish solutions.

Open question in 2025 source

Exact task

Decide solvability of PushPush pathfinding with at most one successful ordered sequence of pushes.

Scale & input

Explicit scalable bounded square grid, block positions, player start and exit.

Move rules

Push one adjacent block until it hits another block or the boundary. No momentum transfer.

Goal

Move the player to the exit, rather than cover storage sites.

Repetition

At most one successful push sequence is promised.

Players & information

One solver, complete information.

Randomness

None in gameplay. The proposed hardness comparison permits randomized reductions.

The cited 2025 source conjectures no polynomial algorithm unless NP = RP. This is not a proved PSPACE-hardness result for the promised version. Later status is not established by this record.

rule change: Blocks slide to obstacles; require a unique push sequence to an exit · Sokoban · Crates onto targets?. This comparison is not itself a reduction.

Open this result in the map

Deciding whether a partial generalized Sudoku has any completion is NP-complete. A fixed 9×9 newspaper puzzle is not the scalable family in this theorem.

NP: completeness

Exact task

Decision: is there a completed grid respecting all givens?

Scale & input

An n²×n² grid with n×n boxes and n² symbols; arbitrary partial instances without a uniqueness promise.

Move rules

Fill blank cells; no sequential move restriction.

Goal

Every row, column and box contains every symbol once.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

No uniqueness promise. The claim is about a growing n²×n² family, not just fixed 9×9 boards. Finding a grid, deciding existence and counting grids are different tasks.

Open this result in the map

A Spiny moving between two tunnels acts as a reusable door. Remembering its position lets a level encode a long computation.

PSPACE: completeness

Exact task

Can Mario reach the flagpole in the supplied level?

Scale & input

Arbitrary explicitly described level. Off-screen sprites persist, or the whole level fits a scalable screen. Timer may grow exponentially.

Move rules

Small Mario, blocks, jumps, Spinies and firebars. Backtracking allowed.

Goal

Reach the flagpole.

Repetition

No ban on revisiting positions.

Players & information

One player; complete level description.

Randomness

Deterministic modeled dynamics.

This is SMB-general, not the fixed NES cartridge or its ordinary screen/reset limits.

Open this result in the map

Forgetting distant objects can make the generalized game efficiently solvable.

P: polynomial-time algorithm

Exact task

Can Mario finish the supplied level or level sequence in the reset model?

Scale & input

Explicitly encoded levels; constant screen size and constant number of on-screen sprites.

Move rules

The SMB-standard reset model of Section 2. Far-off-screen state is forgotten.

Goal

Reach the flagpole or finish the level sequence in the modeled game.

Repetition

Revisits allowed, with the specified resets.

Players & information

One player; complete level description.

Randomness

Deterministic modeled dynamics.

The encoding matters: arbitrary run-length compression is not covered by this P result.

Open this result in the map

Seeing the whole piece sequence still leaves hard packing choices.

NP: completeness

Exact task

Can the known sequence of pieces be placed to clear at least k rows without losing?

Scale & input

Growing rectangular board, initial filled cells, explicit finite piece sequence, row target k.

Move rules

Translate/rotate falling tetrominoes; complete rows clear.

Goal

Clear at least k rows without losing.

Repetition

Finite supplied sequence; no repeating history rule.

Players & information

One player; all future pieces visible.

Randomness

None.

Uses the paper's rotation models, not an assertion about every modern implementation or a fixed 10 × 20 board.

Open this result in the map

Two columns admit a polynomial-time algorithm.

P: polynomial-time algorithm

Exact task

Decide whether the known piece sequence can survive, optionally clearing the board.

Model & rules

Explicit initial board of variable height, fixed width two, explicit tetromino sequence. One informed player, no randomness. Pieces fall, rotate and lock. Full rows disappear. Section 2 uses partial lock-out and specified rotation restrictions.

restriction: Restrict the width from eight columns to two · Eight columns still suffice. This comparison is not itself a reduction.

Open this result in the map

A fixed width of eight preserves NP-completeness.

NP: completeness

Exact task

Decide survival or complete board clearing for the supplied sequence.

Model & rules

Height, initial occupied cells and finite tetromino sequence are input. One informed player, no randomness. Section 2 rotation and partial lock-out rules apply. This is not a fixed 10 × 20 board.

Open this result in the map

A 2026 result gives hardness for each single shape I, T, S, Z, J and L.

NP: completeness (Published NP-hardness plus polynomial certificate verification for an explicit sequence or unary piece count.) [atlas-derived]

Exact task

Decide clearing or survival for the supplied finite run of one piece type.

Scale & input

Explicit growing board, initially filled cells and prescribed number of identical pieces.

Move rules

Super Rotation System (SRS), including wall kicks.

Goal

Clear the board, or place all pieces without losing.

Repetition

Pieces consumed in order.

Players & information

One player. Entire input known.

Randomness

None.

Encoding

The finite sequence is explicitly listed, equivalently a unary count of identical pieces. A compact binary count is a different input model.

O (square) is excluded. The rotation model is essential. Source states NP-hardness.

rule change: Use SRS wall kicks and one piece shape, and change the goal from a row target to clearing the board or surviving the sequence · Tetris · Know every upcoming piece. This comparison is not itself a reduction.

Open this result in the map

With room at the top, indefinite survival is guaranteed and eventual clearing is polynomial-time.

P: polynomial-time algorithm

Exact task

Decide whether the board can eventually be completely cleared with enough I-pieces.

Scale & input

Growing board of height at least 7. Top three rows empty. Unlimited identical I-pieces.

Move rules

Translate and rotate straight tetrominoes under the paper’s model.

Goal

Eventually clear the board.

Repetition

Unlimited supply.

Players & information

One player. Initial board known.

Randomness

None.

Both initial conditions and the supply/goal differ from finite-count hardness.

task change: Only one tetromino shape. This comparison is not itself a reduction.

Open this result in the map

The falling rotation rule allows a polynomial-time algorithm.

P: polynomial-time algorithm

Exact task

Decide survival for a specified count, or eventual clearing with unlimited dominoes.

Scale & input

Growing board. Only 1×2 pieces. Explicit finite count for survival or unlimited supply for eventual clearing.

Move rules

Rotation keeps a lowest cell fixed and moves the other to an unoccupied cell no higher.

Goal

Survive the specified count, or eventually clear.

Repetition

Pieces may continue indefinitely for the latter task.

Players & information

One player. Initial board and supply known.

Randomness

None.

Does not classify clearing with an arbitrarily short prescribed domino count.

rule change: Tetris · Know every upcoming piece. This comparison is not itself a reduction.

Open this result in the map

Pushing a block can make it a future hookshot target. The final route checks whether earlier choices opened every required crossing.

NP: hardness / lower bound · PSPACE: upper bound / membership (Membership applies to the source’s finite-state game model and stated encoding assumptions.)

Exact task

Can Link reach the target using the hookshot rules in this model?

Scale & input

Explicit arbitrary-size dungeon with polynomial-bit coordinates and object state. State needed by the construction persists.

Move rules

Hookshot, movable blocks, treasure chests and crossing paths.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; complete dungeon description.

Randomness

No random element used by the reduction.

This mechanic-based model is NP-hard and in PSPACE. NP-completeness is not established by the original theorem. Persistent object state uses polynomially many bits.

Open this result in the map

Switches make a reusable door network. Gates must remember their state when Link leaves the room.

PSPACE: completeness

Exact task

Can Link reach the target using the switch rules in this model?

Scale & input

Arbitrary-size dungeon. Floor-switch gate states explicitly persist across rooms.

Move rules

Floor switches, gates, crystal switches, pillars and one-way teleporter tiles.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; full dungeon and engine state.

Randomness

Hard construction uses no random behavior. General upper bound uses polynomially encoded engine/seed state.

The cross-room memory assumption is explicit in the theorem, rather than assumed from every Zelda release.

Open this result in the map

The proved construction uses parked minecarts as barriers. Question 1 asks whether that ingredient is necessary.

Open question in 2023 source

Exact task

Determine whether generalized Zelda minecart navigation remains PSPACE-hard without carts blocking walking routes.

Scale & input

Explicit scalable 2D rooms with tracks, carts, start and goal.

Move rules

Ride minecarts, switch T-junctions with levers, retain minecart-only doors. Exclude using parked carts to block walking paths.

Goal

Reach the target location.

Repetition

Revisits and repeated track switches allowed.

Players & information

One solver, complete information.

Randomness

None.

Hardness is open in the cited 2023 source; later status is not established by this record. The question itself supplies no lower bound for this restriction.

Open this result in the map

Each Hex cell can be represented by a 9×9 TwixT gadget.

PSPACE: completeness

Exact task

Decision: can the designated player force a connection?

Scale & input

An arbitrary input position on a growing rectangular grid, including colored pegs and links.

Move rules

Add one peg on a legal empty hole, avoiding the opponent’s border rows or columns. Link same-color pegs a knight’s move apart without crossing links. A player may remove their own links to add others. Pegs stay fixed.

Goal

Connect the player’s two opposite sides.

Repetition

Each turn adds a peg. Game length is bounded by board area.

Players & information

Two players, full information. Input positions are after any opening swap choice.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

Open this result in the map

Allowing links of the same color to cross preserves the hardness construction. Pegs still fill the board permanently, giving a polynomial bound on the number of turns.

PSPACE: completeness [atlas-derived]

Exact task

Determine whether a player can force a connection.

Model & rules

Growing board and arbitrary peg/link position, two players with full information, no chance. Same-color links may cross. Opposite colors cannot cross. Peg count increases each turn.

rule change: Allow crossings between own links · TwixT · Connect opposite sides. This comparison is not itself a reduction.

Open this result in the map

Matching colors or numbers is enough for NP-completeness in the scalable solitaire model.

NP: completeness

Exact task

Decision: is there a legal ordering of every card?

Scale & input

An explicit multiset of cards with color and number labels. Card count and both label sets may grow.

Move rules

Discard one card matching the previous color or number. The first card is unrestricted. No action cards, draw pile or voluntary passes.

Goal

Play all cards.

Repetition

Discarded cards cannot return.

Players & information

One player, all cards known.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

Open this result in the map

The corrected two-player model reduces to undirected vertex Geography.

P: polynomial-time algorithm

Exact task

Decision: can the first player avoid being the first unable to play?

Scale & input

An explicit multiset of cards with color and number labels. Card count and both label sets may grow.

Move rules

Discard one card matching the previous color or number. The first card is unrestricted. No action cards, draw pile or voluntary passes.

Goal

Determine the first player unable to play, under optimal opposition, in the paper’s uncooperative model.

Repetition

Discarded cards cannot return.

Players & information

Two alternating players, both hands visible.

Randomness

None.

Simplified model, not commercial hidden-hand UNO. The authors explicitly withdrew their 2010 PSPACE-completeness claim.

Open this result in the map

Fixing either colors or numbers makes solitaire UNO polynomial-time.

P: polynomial-time algorithm

Exact task

Decide whether every card can be played.

Model & rules

Explicit growing card multiset, same matching rule, no action cards or draws. One player, all information known, no randomness. Each card is discarded once.

restriction: Bound colors or numbers · UNO · Order all the cards. This comparison is not itself a reduction.

Open this result in the map

Cooperation is NP-complete in the scalable visible-hand model.

NP: completeness

Exact task

Can both players cooperate to empty player 1’s hand first?

Model & rules

Two visible hands, unbounded card colors and numbers, no draw pile or action cards. Alternate discards. A stuck player skips rather than loses. No voluntary pass. Cards never return.

rule change: Cooperate, and skip if stuck · UNO · Two players, visible hands. This comparison is not itself a reduction.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Can the supplied 3s positive integers be partitioned into s triples with the same specified sum T?

Scale & input

Partition 3s positive integers into s triples all summing to T, with T/4 < a_i < T/2; unary instances suffice.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Is a conjunction of clauses of three literals satisfiable?

Scale & input

Is a conjunction of clauses of three literals satisfiable?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Can the target edge be reversed legally when each edge may reverse at most once?

Scale & input

An initially acyclic, legally oriented constraint graph using the AND, OR, FANOUT and CHOICE vertex types specified in Sections 1.1–1.3 of the cited paper. Edges have weights 1 or 2 and minimum incoming weight is two.

Move rules

Reverse one edge while maintaining incoming weight at least two at every vertex. Each edge may reverse at most once.

Goal

Reverse the designated target edge.

Repetition

An edge cannot be reversed again. Thus a move sequence has at most the number of edges.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Given a Boolean circuit, is there an input making its output true?

Scale & input

Given a Boolean circuit, is there an input making its output true?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Can the supplied planar weighted AND/OR graph be oriented with incoming weight at least two at every vertex?

Scale & input

A planar graph of AND vertices with incident edge weights 1, 1, 2 and OR vertices with weights 2, 2, 2. Each vertex requires incoming weight at least two.

Move rules

Assign an orientation to every edge. This is a static existence problem with no move sequence.

Goal

Find an orientation satisfying the minimum incoming weight at every vertex.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

A small graph of weighted arrows can encode surprisingly complex sequences. Reversing one chosen arrow is the source problem for the Rush Hour construction.

PSPACE: completeness

Exact task

Decision: can a legal move sequence reverse a designated edge?

Scale & input

Growing planar AND/OR graph, initial legal orientation, designated edge; protected OR restriction is available.

Move rules

Reverse one edge while keeping incoming total weight at least 2 everywhere. AND incident weights 1,1,2; OR weights 2,2,2.

Goal

Reverse the designated edge.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Nondeterministic means a choice of moves, not random outcomes.

Open this result in the map

Here the target specifies every arrow, not just one. This version of constraint logic supplies the Sokoban construction.

PSPACE: completeness

Exact task

Decision: is prescribed legal orientation B reachable from orientation A?

Scale & input

Growing planar AND/OR graph; both complete edge orientations are input.

Move rules

Reverse one edge, always preserving incoming weight ≥2 at every vertex. AND incident weights are 1,1,2; OR incident weights are 2,2,2.

Goal

Match every edge in the target orientation.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Open this result in the map

Choose true variables so that every listed group contains exactly one true variable.

Source: reduction source

Exact task

Can truth values be assigned so exactly one variable is true in every positive clause of at most three variables?

Scale & input

A list of positive clauses, each containing at most three variables.

Move rules

Assign each variable true or false.

Goal

Exactly one true variable per clause.

Repetition

Not applicable.

Players & information

One solver; full formula.

Randomness

None.

This record defines the source problem used by the match-three reduction. Its source coverage is limited to the reduction paper and Schaefer’s bibliographic record and abstract; it carries no separate complexity classification.

Open this result in the map

Players choose previously unchosen variables in any order. One sets theirs true, the other false.

PSPACE: completeness

Exact task

Decision: can the True player force the formula to be true?

Scale & input

A positive CNF formula of arbitrary size.

Move rules

True moves first. Players alternate choosing one unassigned variable; True assigns true and False assigns false.

Goal

True player wants every clause true after all variables are assigned.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Unlike a quantified prefix, players choose the order of variables.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Does the supplied finite induced subgraph of the square lattice have a cycle visiting every vertex exactly once?

Scale & input

Does a finite induced subgraph of the square lattice have a cycle visiting every vertex exactly once? The cited Rubik source excludes degree-one vertices; those are trivially no-instances.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Is the supplied 3CNF formula with planar variable-clause incidence structure satisfiable?

Scale & input

Satisfiability of a 3CNF formula with planar variable-clause incidence structure.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Is the designated output of a planar Boolean circuit made true by some input assignment?

Scale & input

Is the designated output of a planar Boolean circuit made true by some input assignment?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Source: reduction source

Exact task

Does a planar graph of maximum degree three have a Hamiltonian cycle?

Scale & input

Does a planar graph of maximum degree three have a Hamiltonian cycle?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Open this result in the map

Imagine two players choosing true or false values in a fixed order. One wants the final formula true, the other false. This is a starting point for game reductions.

PSPACE: completeness

Exact task

Is a fully quantified Boolean formula, in prenex form with a conjunctive-normal-form (CNF) matrix, true?

Scale & input

Explicit sequence of quantifiers followed by a CNF formula (an AND of clauses, each an OR of literals). The formula and number of variables grow.

Move rules

Existential and universal choices follow the quantifier order; the final assignment is evaluated.

Goal

The existential chooser wants true; the universal chooser wants false.

Repetition

Each variable is assigned once.

Players & information

Two choosers; all earlier choices visible

Randomness

None

This hub uses the quantified-CNF decision problem. The game analogy explains the quantifiers; there is no random assignment.

Open this result in the map

Connect given points with horizontal and vertical segments, keeping the total length within a budget. This network-design problem supplies the hardness proof for short sliding-tile solutions.

NP: completeness

Exact task

Decision: can integer-coordinate terminals be connected by a rectilinear tree of total length ≤ℓ?

Scale & input

Variable number of plane terminals and input length budget.

Move rules

Not sequential: choose horizontal/vertical segments and optional junctions.

Goal

A connected tree through every terminal within the budget.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Open this result in the map