Saturation and stability in the theory of computation over the reals
type: Item
instance of: scholarly article
title: Saturation and stability in the theory of computation over the reals
zbMATH Open document ID: 0930.03044
DOI: 10.1016/S0168-0072(98)00060-8
author: Olivier Chapuis
author: Pascal Koiran
published in: Annals of Pure and Applied Logic
publication date: 2000-02-08T00:00:00Z
review text: This paper deals with computational complexity over structures for first-order languages. In particular, the authors obtain several results concerning /const complexity classes (as introduced by Michaux) for real-closed fields and ordered vector spaces over the rationals.
reviewed by: Leon Harkleroad
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03C07
Mathematics Subject Classification ID: 03C99
Mathematics Subject Classification ID: 12L12
zbMATH DE Number: 1339978
zbMATH Keywords: real-closed field
zbMATH Keywords: computational complexity
zbMATH Keywords: parallel computation
zbMATH Keywords: ordered vector spaces
MaRDI profile type: Publication
cites work: Q4039803
cites work: Q3996675
cites work: Q4717931
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q3770650
cites work: \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
cites work: On the Complexity of Quantifier Elimination: the Structural Approach
cites work: On the Power of Real Turing Machines over Binary Inputs
cites work: Computing over the reals with addition and order: Higher complexity classes
cites work: Separation of complexity classes in Koiran's weak model
cites work: Q4723875
cites work: Accessible telephone directories
cites work: Sur la complexité du principe de Tarski-Seidenberg
cites work: Q4542570
cites work: Q4003410
cites work: Definable Sets in Ordered Structures. II
cites work: Turing machines that take advice
cites work: Computing over the reals with addition and order
cites work: A weak version of the Blum, Shub, and Smale model
cites work: Elimination of constants from machines over algebraically closed fields
cites work: On the Structure of Polynomial Time Reducibility
cites work: Elimination of quantifiers in algebraic structures
cites work: On the Structure of $\cal NP_\Bbb C$
cites work: Definable types in -minimal theories
cites work: P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
cites work: Some remarks on definable equivalence relations in O-minimal structures
cites work: Definable Sets in Ordered Structures. I
cites work: Q3707983
cites work: Q4841154
cites work: On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
cites work: Real addition and the polynomial hierarchy
cites work: Q4724607
cites work: Q3837729
cites work: Q4392286
cites work: Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
description: scientific article; zbMATH DE number 1339978