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: | Christian Herrmann, Johanna Sokoli, Martin Ziegler |
---|---|
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 |
Similar Items
-
Noncomputable functions in the Blum-Shub-Smale model
by: Wesley Calvert, et al.
Published: (2011-05-01) -
Modification to queueing system M/M/1 with Blum-Blum-Shub generator
by: Jaffara, M. Z. A. M., et al.
Published: (2022) -
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
by: Murray, Cody (Cody Daniel), et al.
Published: (2021) -
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
by: Murray, Cody D, et al.
Published: (2021) -
blum lagi
by: Muhamad Roslan Rahim, 1982-, author 653661, et al.
Published: (2024)