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