Recent progress on the complexity of the decision problem for the reals

MaRDI QIDQ4391222zbMATH OpenFDO

Authors James Renegar

Publication date 13 September 1998

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10) Complexity of computation (including implicit computational complexity) (03D15) Decidability and field theory (12L05)

Review text

Reprinted from: Discrete and computational geometry, Proc. DIMACS Spec. Year Workshops 1989-1990, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 6, 287-308 (1991; Zbl 0741.03004). For the entire collection see [Zbl 0906.03033].

Recommendations

• scientific article; zbMATH DE number 66690
• On the decisional complexity of problems over the reals
• Computable decision making on the reals and other spaces. Via partiality and nondeterminism
• scientific article; zbMATH DE number 2063216
• Semi-algebraic decision complexity, the real spectrum, and degree
• On the complexity of computable real sequences
• A new approach to computability over the reals
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• Kolmogorov Complexity Theory over the Reals
• -complete decision procedures for satisfiability over the reals

Cited in

(3)

• Recent advances in real complexity and computation. UIMP-RSME Lluís Santaló summer school, Universidad Internacional Menéndez Pelayo, Santander, Spain, July 16--20, 2012
• scientific article; zbMATH DE number 66690 (Why is no real title available?)
• Complexity, exactness, and rationality in polynomial optimization

This page was built for publication: Recent progress on the complexity of the decision problem for the reals

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