Separation of complexity classes in Koiran's weak model
From MaRDI portal
Publication:1338212
DOI10.1016/0304-3975(94)00069-7zbMath0819.68053OpenAlexW2030220007WikidataQ57733307 ScholiaQ57733307MaRDI QIDQ1338212
Michael Shub, Felipe Cucker, Stephen Smale
Publication date: 27 November 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00069-7
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the complexity of quadratic programming in real number models of computation ⋮ Complexity of Bezout's theorem. V: Polynomial time ⋮ Generalized Knapsack problems and fixed degree separations ⋮ On NP-completeness for linear machines ⋮ On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)? ⋮ On Ladner's result for a class of real machines with restricted use of constants ⋮ A weak version of the Blum, Shub, and Smale model ⋮ On the computation of Boolean functions by analog circuits of bounded fan-in ⋮ On sparseness and Turing reducibility over the reals ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants ⋮ On sparseness, reducibilities, and complexity ⋮ Complexity aspects of a semi-infinite optimization problem† ⋮ Saturation and stability in the theory of computation over the reals ⋮ Real computations with fake numbers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- Real quantifier elimination is doubly exponential
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
- A note on a \(P \neq NP\) result for a restricted class of real machines
- Computing over the reals with addition and order
- Complexity of Presburger arithmetic with fixed quantifier dimension
- On the Complexity of Quantifier Elimination: the Structural Approach
- On digital nondeterminism
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
This page was built for publication: Separation of complexity classes in Koiran's weak model
