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 algebraic geometry / polynomial systems, have been shown complete (under many-one reduction by polynomial-time Turing machines) for this class. We exhibit a new one based on questions about expressions built from cross products only.

In Turlough Neary and Matthew Cook: Proceedings Machines, Computations and Universality 2013 (MCU 2013), Zürich, Switzerland, 9/09/2013 - 11/09/2013, Electronic Proceedings in Theoretical Computer Science 128, pp. 85–92.
Published: 4th September 2013.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: