Saturation and stability in the theory of computation over the reals
From MaRDI portal
Publication:1304539
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)
03C99: Model theory
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
12L12: Model theory of fields
03C07: Basic properties of first-order languages and structures
Related Items
Weak arithmetics, Weak arithmetic, On Ladner's result for a class of real machines with restricted use of constants, VPSPACE and a transfer theorem over the complex field, Elimination of parameters in the polynomial hierarchy, Some aspects of studying an optimization or decision problem in different computational models, 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
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
