The complexity of local dimensions for constructible sets

DOI10.1006/jcom.1999.0536zbMath0951.68043OpenAlexW2026869748MaRDI QIDQ1977150

Pascal Koiran

Publication date: 9 May 2000

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

Full work available at URL: https://semanticscholar.org/paper/2d9dfa14d367f7567c21bf680abc5b4b16c9bf8f

zbMATH Keywords

Arthur-Merlin class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

What else is undecidable about loops?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability and fast quantifier elimination in algebraically closed fields
• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Elimination of parameters in the polynomial hierarchy
• Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Sharp Effective Nullstellensatz

This page was built for publication: The complexity of local dimensions for constructible sets