Saturation and stability in the theory of computation over the reals

DOI10.1016/S0168-0072(98)00060-8zbMath0930.03044MaRDI QIDQ1304539

Pascal Koiran, Olivier Chapuis

Publication date: 8 February 2000

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

computational complexityreal-closed fieldparallel computationordered vector spaces

Mathematics Subject Classification ID

Model theory (03C99) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Model theory of fields (12L12) Basic properties of first-order languages and structures (03C07)

Related Items (12)

Algorithms yield upper bounds in differential algebra ⋮ On Ladner's result for a class of real machines with restricted use of constants ⋮ The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete. ⋮ A note on non-complete problems in \(NP_\mathbb{R}\) ⋮ An explicit solution to Post's problem over the reals ⋮ On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants ⋮ Weak arithmetics ⋮ Weak arithmetic ⋮ VPSPACE and a transfer theorem over the complex field ⋮ Elimination of parameters in the polynomial hierarchy ⋮ Interactive proofs and a Shamir-like result for real number computations ⋮ Some aspects of studying an optimization or decision problem in different computational models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A weak version of the Blum, Shub, and Smale model
• Turing machines that take advice
• Elimination of quantifiers in algebraic structures
• Real addition and the polynomial hierarchy
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Separation of complexity classes in Koiran's weak model
• Computing over the reals with addition and order
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• Elimination of constants from machines over algebraically closed fields
• Computing over the reals with addition and order: Higher complexity classes
• On the Complexity of Quantifier Elimination: the Structural Approach
• Some remarks on definable equivalence relations in O-minimal structures
• Definable Sets in Ordered Structures. I
• Definable Sets in Ordered Structures. II
• On the Structure of Polynomial Time Reducibility
• On the Structure of $\cal NP_\Bbb C$
• Accessible telephone directories
• Definable types in -minimal theories
• On the Power of Real Turing Machines over Binary Inputs
• Sur la complexité du principe de Tarski-Seidenberg
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function

This page was built for publication: Saturation and stability in the theory of computation over the reals