arXiv:2611.10481
A trace costs one quantifier: the exact complexity of perfect play in nonlocal games
Seth Douglas, Nidhal Mghirbi
Abstract
Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is Σ⁰₂-complete, even when restricted to games of value one, so it cannot be decided even with an oracle for the halting problem. This is strictly harder than perfect play in the finite-dimensional and commuting-operator models, which are Σ⁰₁-complete and Π⁰₁-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is Σ⁰₂-complete, whereas for every fixed type III_λ subtype it has the same Π⁰₁-complete language as unrestricted commuting play. A trace thus costs one existential number quantifier: the hardness constructions force every perfect strategy to choose a finite clock period or a finite tree depth. The spatial classification persists when finite entanglement entropy is required, and it is formally verified in Lean, assuming only a special case of Tarski's decision theorem. We also prove Σ⁰₂-completeness for one-shot zero-error communication with normal entanglement, and construct a finite channel with zero-error codes of a given size every one of which needs infinite entanglement entropy.