Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines
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)...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Open Publishing Association
2013-09-01
|
Series: | Electronic Proceedings in Theoretical Computer Science |
Online Access: | http://arxiv.org/pdf/1309.1270v1 |
Summary: | 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. |
---|---|
ISSN: | 2075-2180 |