  The foundations of classical Algebraic Geometry and Real Algebraic Geometry
are the Nullstellensatz and Positivstellensatz. Over the last two decades the
basic analogous theorems for matrix and operator theory (noncommutative
variables) have emerged. This paper concerns commuting operator strategies for
nonlocal games, recalls NC Nullstellensatz which are helpful, extends these,
and applies them to a very broad collection of games. In the process it brings
together results spread over different literatures, hence rather than being
terse, our style is fairly expository.
  The main results of this paper are two characterizations, based on
Nullstellensatz, which apply to games with perfect commuting operator
strategies. The first applies to all games and reduces the question of whether
or not a game has a perfect commuting operator strategy to a question involving
left ideals and sums of squares. Previously, Paulsen and others translated the
study of perfect synchronous games to problems entirely involving a
$*$-algebra.The characterization we present is analogous, but works for all
games. The second characterization is based on a new Nullstellensatz we derive
in this paper. It applies to a class of games we call torically determined
games, special cases of which are XOR and linear system games. For these games
we show the question of whether or not a game has a perfect commuting operator
strategy reduces to instances of the subgroup membership problem and, for
linear systems games, we further show this subgroup membership characterization
is equivalent to the standard characterization of perfect commuting operator
strategies in terms of solution groups. Both the general and torically
determined games characterizations are amenable to computer algebra techniques,
which we also develop.
