scientific article; zbMATH DE number 176763

MaRDI QIDQ4036593zbMATH OpenFDO

Authors Felipe Cucker, A. Torrecillas

Publication date 18 May 1993

zbMATH Keywords

computational complexityalgebraic complexity\(P\)-complete problems for the real model

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Applications of computability and recursion theory (03D80)

Recommendations

• Two \(P\)-complete problems in the theory of the reals
• NC algorithms for real algebraic numbers
• scientific article; zbMATH DE number 1775437
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• 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

Cited in

(8)

• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• scientific article; zbMATH DE number 1775437 (Why is no real title available?)
• A problem that is easier to solve on the unit-cost algebraic RAM
• Fundamentals of Computation Theory
• Lower bounds for arithmetic networks
• A completion problem over the field of real numbers
• An explicit solution to Post's problem over the reals

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036593)