Exotic quantifiers, complexity classes, and complete problems

DOI10.1007/s10208-007-9006-9zbMath1185.68343OpenAlexW2101230787WikidataQ57733138 ScholiaQ57733138MaRDI QIDQ1022429

Peter Bürgisser, Felipe Cucker

Publication date: 22 June 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-007-9006-9

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The Legacy of Turing in Numerical Analysis, The complexity of the Hausdorff distance, On Ladner's result for a class of real machines with restricted use of constants, Computing the homology of real projective sets, Grid methods in computational real algebraic (and semialgebraic) geometry, The real computational complexity of minmax value and equilibrium refinements in multi-player games, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Unnamed Item, Computing the homology of semialgebraic sets. I: Lax formulas, On the computational complexity of decision problems about multi-player Nash equilibria, Computational complexity of multi-player evolutionarily stable strategies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A weak version of the Blum, Shub, and Smale model
• The complexity of semilinear problems in succinct representation
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• The polynomial-time hierarchy
• Computing over the reals with addition and order
• Generalized Knapsack problems and fixed degree separations
• Completeness and reduction in algebraic complexity theory
• Computing over the reals with addition and order: Higher complexity classes
• The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• On the Complexity of Quantifier Elimination: the Structural Approach
• On the Complexity of Numerical Analysis
• Logics which capture complexity classes over the reals
• On the Power of Real Turing Machines over Binary Inputs
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Counting Complexity Classes for Numeric Computations I: Semilinear Sets
• Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
• On digital nondeterminism
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Recursive Predicates and Quantifiers
• Algorithms in real algebraic geometry
• Derandomizing polynomial identity tests means proving circuit lower bounds