  We investigate the connection between the complexity of nonlocal games and
the arithmetical hierarchy, a classification of languages according to the
complexity of arithmetical formulas defining them. It was recently shown by Ji,
Natarajan, Vidick, Wright and Yuen that deciding whether the
(finite-dimensional) quantum value of a nonlocal game is $1$ or at most
$\frac{1}{2}$ is complete for the class $\Sigma_1$ (i.e., $\mathsf{RE}$). A
result of Slofstra implies that deciding whether the commuting operator value
of a nonlocal game is equal to $1$ is complete for the class $\Pi_1$ (i.e.,
$\mathsf{coRE}$). We prove that deciding whether the quantum value of a
two-player nonlocal game is exactly equal to $1$ is complete for $\Pi_2$; this
class is in the second level of the arithmetical hierarchy and corresponds to
formulas of the form "$\forall x \, \exists y \, \phi(x,y)$". This shows that
exactly computing the quantum value is strictly harder than approximating it,
and also strictly harder than computing the commuting operator value (either
exactly or approximately). We explain how results about the complexity of
nonlocal games all follow in a unified manner from a technique known as
compression. At the core of our $\Pi_2$-completeness result is a new "gapless"
compression theorem that holds for both quantum and commuting operator
strategies. Our compression theorem yields as a byproduct an alternative proof
of Slofstra's result that the set of quantum correlations is not closed. We
also show how a "gap-preserving" compression theorem for commuting operator
strategies would imply that approximating the commuting operator value is
complete for $\Pi_1$.
