pith. sign in

arxiv: 1309.1270 · v1 · pith:CQ5DG3PKnew · submitted 2013-09-05 · 💻 cs.CC · cs.LO

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

Christian Herrmann , Johanna Sokoli , Martin Ziegler This is my paper
classification 💻 cs.CC cs.LO
keywords machinesblum-shub-smaleclasscompletecrossnondeterministicpolynomial-timereal
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Smoothed Analysis of Order Types

    cs.CG 2019-07 unverdicted novelty 7.0

    Order type realizability, ∃R-complete in the worst case, can be decided in expected NP time under smoothed analysis.