Two \(P\)-complete problems in the theory of the reals

DOI10.1016/0885-064X(92)90008-YzbMath0759.68032WikidataQ57733324 ScholiaQ57733324MaRDI QIDQ1203649

A. Torrecillas, Felipe Cucker

Publication date: 22 February 1993

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

zbMATH Keywords

PRAMalgebraic complexityparallel complexity classesparallel algorithms over the realsreal circuit decision problemsystems of equations solvable by substitution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

A note on non-complete problems in \(NP_\mathbb{R}\), A size-depth trade-off for the analog computation of Boolean functions, On the computation of Boolean functions by analog circuits of bounded fan-in, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture, On digital nondeterminism, Exotic quantifiers, complexity classes, and complete problems, Logics which capture complexity classes over the reals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Complete problems for deterministic polynomial time
• On the computational power of pushdown automata
• Simulation of Parallel Random Access Machines by Circuits
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines