Saturation and stability in the theory of computation over the reals (Q1304539): Difference between revisions

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.

0 references

reviewed by

Leon Harkleroad

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

real-closed field

0 references

computational complexity

0 references

parallel computation

0 references

ordered vector spaces

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

0 references

On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

0 references

Q3770650

0 references

$P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}$

0 references

On the Complexity of Quantifier Elimination: the Structural Approach

0 references

On the Power of Real Turing Machines over Binary Inputs

0 references

Computing over the reals with addition and order: Higher complexity classes

0 references

Separation of complexity classes in Koiran's weak model

0 references

Q4723875

0 references

Accessible telephone directories

0 references

Sur la complexité du principe de Tarski-Seidenberg

0 references

Q4542570

0 references

Q4003410

0 references

Definable Sets in Ordered Structures. II

0 references

Turing machines that take advice

0 references

Computing over the reals with addition and order

0 references

A weak version of the Blum, Shub, and Smale model

0 references

Elimination of constants from machines over algebraically closed fields

0 references

On the Structure of Polynomial Time Reducibility

0 references

Elimination of quantifiers in algebraic structures

0 references

On the Structure of $\cal NP_\Bbb C$

0 references

Definable types in -minimal theories

0 references

P$\neq$NP over the nonstandard reals implies P$\neq$NP over $\mathbb{R}$

0 references

Some remarks on definable equivalence relations in O-minimal structures

0 references

Definable Sets in Ordered Structures. I

0 references

Q3707983

0 references

Q4841154

0 references

On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination

0 references

Real addition and the polynomial hierarchy

0 references

Q4724607

0 references

Q3837729

0 references

Q4392286

0 references

Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1304539

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