Exotic quantifiers, complexity classes, and complete problems
From MaRDI portal
Recommendations
- Exotic Quantifiers, Complexity Classes, and Complete Problems
- On complete problems, relativizations and logics for complexity classes
- Complexity classes defined by counting quantifiers
- scientific article; zbMATH DE number 3845566
- scientific article; zbMATH DE number 4075030
- scientific article; zbMATH DE number 4059375
- A note on complete problems for complexity classes
- Capturing complexity classes with Lindström quantifiers
- Qualitative relativizations of complexity classes
- Complete sets and closeness to complexity classes
Cites work
- scientific article; zbMATH DE number 3944020 (Why is no real title available?)
- scientific article; zbMATH DE number 52177 (Why is no real title available?)
- scientific article; zbMATH DE number 953024 (Why is no real title available?)
- scientific article; zbMATH DE number 3227195 (Why is no real title available?)
- A weak version of the Blum, Shub, and Smale model
- Algorithms in real algebraic geometry
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Completeness and reduction in algebraic complexity theory
- Computing over the reals with addition and order
- Computing over the reals with addition and order: Higher complexity classes
- Counting Complexity Classes for Numeric Computations I: Semilinear Sets
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Generalized Knapsack problems and fixed degree separations
- Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
- Logics which capture complexity classes over the reals
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On digital nondeterminism
- On the Complexity of Numerical Analysis
- On the Complexity of Quantifier Elimination: the Structural Approach
- On the Power of Real Turing Machines over Binary Inputs
- 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
- Recursive Predicates and Quantifiers
- The complexity of semilinear problems in succinct representation
- The polynomial-time hierarchy
- The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
- Two \(P\)-complete problems in the theory of the reals
- \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
Cited in
(17)- A complexity theory of constructible functions and sheaves
- 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
- Grid methods in computational real algebraic (and semialgebraic) geometry
- A theory of complexity, condition, and roundoff
- Exotic Quantifiers, Complexity Classes, and Complete Problems
- scientific article; zbMATH DE number 7559416 (Why is no real title available?)
- On the computational complexity of decision problems about multi-player Nash equilibria
- Computing the homology of semialgebraic sets. I: Lax formulas
- Beyond the Existential Theory of the Reals
- On the Complexity of Quantifier Elimination: the Structural Approach
- The real computational complexity of minmax value and equilibrium refinements in multi-player games
- Computing the homology of real projective sets
- QUIXO is EXPTIME-complete
- Computational complexity of multi-player evolutionarily stable strategies
- Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
This page was built for publication: Exotic quantifiers, complexity classes, and complete problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1022429)
