Separation of complexity classes in Koiran's weak model

DOI10.1016/0304-3975(94)00069-7zbMath0819.68053DBLPjournals/tcs/CuckerSS94OpenAlexW2030220007WikidataQ57733307 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

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

Related Items (15)

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