Elimination of parameters in the polynomial hierarchy

DOI10.1016/S0304-3975(98)00261-8zbMath0913.68081MaRDI QIDQ1285590

Pascal Koiran

Publication date: 28 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexitypolynomial hierarchy

Mathematics Subject Classification ID

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

Related Items

The complexity of local dimensions for constructible sets ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Definability of Geometric Properties in Algebraically Closed Fields ⋮ A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density

Cites Work

• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Saturation and stability in the theory of computation over the reals
• Elimination of constants from machines over algebraically closed fields
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item