The complexity of local dimensions for constructible sets
From MaRDI portal
Publication:1977150
DOI10.1006/jcom.1999.0536zbMath0951.68043MaRDI QIDQ1977150
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
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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