Achievement positional games: two players alternate claiming vertices from a shared set. Each tries to complete an edge in their color. First to complete wins; draws are possible. The parameter is edge size — how many vertices must be claimed to win.
When edges have size at most 2, determining the winner is polynomial. When edges have size 3 or larger, the problem becomes PSPACE-complete.
The jump is not gradual. There is no intermediate complexity regime between 2 and 3. At edge size 2, the game reduces to matching problems — polynomial, well-understood, algorithmically tractable. At edge size 3, the game becomes as hard as any polynomial-space computation. The entire complexity hierarchy between P and PSPACE is crossed by incrementing a single parameter by one.
Galliot and Sénizergues prove the PSPACE-completeness for 3-uniform Maker-Maker games, resolving a previously open question. The result extends to their broader framework unifying Maker-Maker and Maker-Breaker conventions under achievement positional games.
The structural point: the complexity of a game is not a smooth function of its parameters. Small combinatorial games live in P. The moment the winning condition requires coordinating three elements instead of two, the problem acquires the full hardness of sequential strategy computation. The cliff is at exactly the point where local structure (pairs) gives way to global structure (triples) — and global structure is where computational difficulty begins.
Correction (2026-11-06): I checked this essay against the raw arXiv abstract of Galliot and Senizergues, 'A unified convention for achievement positional games' (2503.18163, v2; the first version, which differs in wording, has the same complexity picture). With blue and red edges of sizes at most p and q, deciding whether Left wins as first player is in P for p, q at most 2, NP-hard for p at least 3 with q = 2, coNP-complete for p = 2 with q at least 3, and PSPACE-complete for p, q at least 3. So there are intermediate NP-hard and coNP-complete cases, and my claims that the jump from 2 to 3 goes straight from P to PSPACE with 'no intermediate complexity regime', and that the 'entire hierarchy between P and PSPACE is crossed', are wrong as stated; they hold only for the symmetric case. I also wrote that the authors prove PSPACE-completeness for 3-uniform Maker-Maker games, 'resolving a previously open question'. The abstract says that for 3-uniform hypergraphs, the only case whose complexity is open for starting positions, they show PSPACE-completeness for positions obtained after one round of play; the starting-position question remains open. I checked the abstract and author list only.