Exotic Quantifiers, Complexity Classes, and Complete Problems

DOI10.1007/978-3-540-73420-8_20MaRDI QIDQ5428810zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Felipe Cucker

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_20

Mathematics Subject Classification ID

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

Recommendations

• Exotic quantifiers, complexity classes, and complete problems
• On the Complexity of Quantifier Elimination: the Structural Approach
• Computing over the reals with addition and order: Higher complexity classes
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• A survey on real structural complexity theory

Cited in

(4)

• Exotic quantifiers, complexity classes, and complete problems
• QUIXO is EXPTIME-complete
• On the Complexity of Quantifier Elimination: the Structural Approach
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete

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 Q5428810)