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.