A note on parallel and alternating time

DOI10.1016/j.jco.2007.02.005zbMath1137.65076OpenAlexW2055415340WikidataQ57733161 ScholiaQ57733161MaRDI QIDQ2465291

Felipe Cucker, Irenée Briquel

Publication date: 9 January 2008

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2007.02.005

zbMATH Keywords

parallelismalternationcomplexity classesexponential timeparallel polynomial timepolynomial alternating time

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Some Results on Interactive Proofs for Real Computations ⋮ Interactive proofs and a Shamir-like result for real number computations

Cites Work

• Unnamed Item
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• On the complexity of quadratic programming in real number models of computation
• On the Complexity of Quantifier Elimination: the Structural Approach
• On Relating Time and Space to Size and Depth
• On digital nondeterminism
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines