Id: arxiv/2611.10481 Url: https://arxiv.org/abs/2611.10481 Tags: quant-ph, math.LO, math.OA Score: 1 Title: A trace costs one quantifier: the exact complexity of perfect play in nonlocal games Domain: quant-ph Source: arxiv Authors: Seth Douglas, Nidhal Mghirbi Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-07 Reactions: up=1 Page: https://delphi.science/r/arxiv/2611.10481 Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is $Σ^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 $Σ^0_1$-complete and $Π^0_1$-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is $Σ^0_2$-complete, whereas for every fixed type $\mathrm{III}_λ$…