Hilbert's Nullstellensatz is in the polynomial hierarchy
From MaRDI portal
Publication:2365408
DOI10.1006/jcom.1996.0019zbMath0862.68053OpenAlexW2087392392MaRDI QIDQ2365408
Publication date: 4 February 1997
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/d4e687c5dc96a0e4fd47465792f7b6f694a85e7a
Related Items
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Reductions modulo primes of systems of polynomial equations and algebraic dynamical systems ⋮ Knottedness is in NP, modulo GRH ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The complexity of local dimensions for constructible sets ⋮ Cook's versus Valiant's hypothesis ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Efficient algorithms for sparse cyclotomic integer zero testing ⋮ Unnamed Item ⋮ The complexity of tensor rank ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ Smale’s 17th problem: Average polynomial time to compute affine and projective solutions ⋮ Unnamed Item ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ Elimination of parameters in the polynomial hierarchy ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Linear projections of the Vandermonde polynomial ⋮ On the complexity of torus knot recognition ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ The computational complexity of some problems of linear algebra
