Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines

Christian Herrmann, Johanna Sokoli, Martin Ziegler

Nondeterministic polynomial-time Blum-Shub-Smale Machines over the reals give rise to a discrete complexity class between NP and PSPACE. Several problems, mostly from real algebrai…