Exotic quantifiers, complexity classes, and complete problems
type: Item
instance of: scholarly article
title: Exotic quantifiers, complexity classes, and complete problems
zbMATH Open document ID: 1185.68343
author: Peter Bürgisser
author: Felipe Cucker
published in: Foundations of Computational Mathematics
publication date: 2009-06-22T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5567062
MaRDI profile type: Publication
full work available at URL: s10208-007-9006-9
OpenAlex ID: W2101230787
Wikidata QID: Q57733138
cites work: On the Complexity of Numerical Analysis
cites work: Algorithms in real algebraic geometry
cites work: Q5515497
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Implicit Complexity over an Arbitrary Structure: Sequential and Parallel Polynomial Time
cites work: Q3715247
cites work: Completeness and reduction in algebraic complexity theory
cites work: Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
cites work: Counting Complexity Classes for Numeric Computations I: Semilinear Sets
cites work: The complexity of semilinear problems in succinct representation
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: On digital nondeterminism
cites work: Logics which capture complexity classes over the reals
cites work: Generalized Knapsack problems and fixed degree separations
cites work: Two \(P\)-complete problems in the theory of the reals
cites work: Q4717945
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Recursive Predicates and Quantifiers
cites work: Computing over the reals with addition and order
cites work: A weak version of the Blum, Shub, and Smale model
cites work: The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
cites work: Q4002529
cites work: Q1185456
cites work: The polynomial-time hierarchy
DOI: 10.1007/S10208-007-9006-9
DBLP publication ID: journals/focm/BurgisserC09
Recommended article: Exotic Quantifiers, Complexity Classes, and Complete Problems
Recommended article: On Complete Problems, Relativizations and Logics for Complexity Classes
Recommended article: Complexity classes defined by counting quantifiers
Recommended article: Q3315499
Recommended article: Q3807183
Recommended article: Q3794168
Recommended article: A note on complete problems for complexity classes
Recommended article: Capturing complexity classes with Lindström quantifiers
Recommended article: Qualitative relativizations of complexity classes
Recommended article: Complete sets and closeness to complexity classes
description: scientific article; zbMATH DE number 5567062