TL;DR
This paper proves that three popular, modern video games—Baba Is You, Fez, and Catherine—are NP-hard. By constructing clever "gadgets" within each game's unique mechanics, the authors demonstrate that solving a level in these games is computationally equivalent to solving the classic 3-SAT logic problem.
What Problem Does This Paper Address?
Computational complexity theory seeks to classify how "hard" a problem is to solve for a computer. While early research focused on games like Chess, the last two decades have seen a surge in analyzing video games. Proving a game is NP-hard means there is no known "fast" (polynomial-time) algorithm to solve every possible level; as the levels get larger, the time required to find a solution grows exponentially.
The authors aim to fill a gap in the literature by providing formal hardness results for three recent hits that utilize 2D, 2.5D, and 3D mechanics. Crucially, they aimed to keep the proofs "simple enough to be shown in an undergraduate algorithms course," making the complex world of theoretical computer science more accessible through familiar media.
Methods
The researchers used a standard technique called polynomial-time reduction. Specifically, they reduced the 3-SAT problem (a known NP-complete problem involving boolean logic) to each game.
To do this, they designed "gadgets" within each game's engine:
- Variable Gadgets: Represent a boolean variable ($x$) that can be set to either True or False.
- Clause Gadgets: Represent a logical constraint (e.g., "$x$ or $y$ or $z$ must be true").
- Wiring: A way to connect these gadgets so that a player can only "win" the level if they find a valid assignment of True/False values that satisfies all logical constraints.
Datasets
As a theoretical computer science paper, no external datasets or training sets were used. The "data" consists of the core mechanics and rulesets of the three games:
- Baba Is You: A 2D puzzle game where players push blocks to rewrite the rules of the game (e.g., "WALL IS STOP" or "ROCK IS PUSH").
- Fez: A "2.5D" platformer where the player rotates a 3D world to see four different 2D perspectives.
- Catherine: A 3D puzzle-climber where the player moves blocks to ascend a tower while a "death plane" rises from below.
Key Insights and Ideas
- Rule Manipulation as Logic: In Baba Is You, the authors used the "DEFEAT" and "YOU" modifiers to create pathways. If a player chooses a path representing a "False" assignment, they might trigger a rule that destroys their character, effectively enforcing logical consistency through the game's own rule-rewriting engine.
- Perspective as State: In Fez, the "aha moment" is using the four faces of a 3D column to represent variable states. By rotating the world, the player chooses which "face" (literal) is active. The authors used the game's jumping physics—specifically the maximum horizontal distance Gomez can jump—to ensure players couldn't "skip" the logic of the clause gadgets.
- Physics-Based Constraints: In Catherine, the authors leveraged the "edge property" (blocks stay up if even one edge touches another) and "cracked blocks" (which break after limited use). These mechanics were used to create a "one-way" logic flow, preventing players from reusing blocks or backtracking in ways that would break the 3-SAT reduction.
Key Results
- Baba Is You is NP-hard: The ability to change rules on the fly allows for the creation of complex logic gates.
- Fez is NP-hard: The perspective-shifting mechanic, combined with movement constraints, is sufficient to encode 3-SAT.
- Catherine is NP-complete: The authors proved not only that it is NP-hard, but also that it is in the class NP (meaning a solution can be verified quickly). This makes it NP-complete, the "gold standard" of computational difficulty.
- Undergraduate Accessibility: The paper successfully demonstrates that high-level complexity results can be derived from intuitive, visual game mechanics rather than just abstract symbols.
Limitations and Future Work
The authors note that while they proved NP-hardness, some of these games might be even harder. For example, many block-pushing games are actually PSPACE-complete (requiring even more computational resources than NP-hard problems).
The Catherine proof relies on a "death plane" (a timer) to keep the game in NP; without a time limit, the complexity might shift. Future work could explore whether these games remain hard under more restrictive conditions (e.g., limited types of blocks) or if they reach higher complexity classes like PSPACE or even undecidability.
Summary updated