A trace costs one quantifier: the exact complexity of perfect play in nonlocal games

arXiv:2611.10481v1 Announce Type: new Abstract: Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is $\Sigma^0_2$-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 $\Sigma^0_1$-complete and $\Pi^0_1$-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is $\Sigma^0_2$-complete, whereas for every fixed type $\mathrm{III}_\lambda$ subtype it has the same $\Pi^0_1$-complete language as unrestricted commuting play.