Elimination of constants from machines over algebraically closed fields

DOI10.1006/jcom.1997.0433zbMath0878.68066OpenAlexW1984469422MaRDI QIDQ1361877

Pascal Koiran

Publication date: 26 August 1997

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

Full work available at URL: https://semanticscholar.org/paper/0ac6e3306791b66cc3da08c9cb1800d1b8214382

zbMATH Keywords

discrete complexity theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On sets of linear forms of maximal complexity ⋮ The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete. ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Elimination of parameters in the polynomial hierarchy ⋮ Saturation and stability in the theory of computation over the reals

Cites Work

• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• A note on a \(P \neq NP\) result for a restricted class of real machines
• A survey on real structural complexity theory
• On the efficiency of effective Nullstellensätze
• Shattering All Sets of ‘k’ Points in “General Position” Requires (k — 1)/2 Parameters
• Accessible telephone directories
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On $ω_1$-categorical theories of fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item