On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?

DOI10.1215/S0012-7094-95-08105-8zbMath0882.03040OpenAlexW2082560626WikidataQ56697964 ScholiaQ56697964MaRDI QIDQ1913573

Michael Shub, Stephen Smale

Publication date: 24 June 1996

Published in: Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1215/s0012-7094-95-08105-8

zbMATH Keywords

polynomial time algorithmintractabilityalgebraic algorithmsdecision algorithmHilbert nullstellensatz

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Decidability (number-theoretic aspects) (11U05) Complexity of computation (including implicit computational complexity) (03D15) Relevant commutative algebra (14A05)

Related Items (21)

Derandomization from Algebraic Hardness ⋮ Polynomial automorphisms and Gröbner reductions ⋮ The foundations of spectral computations via the solvability complexity index hierarchy ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ On asymptotic estimates for arithmetic cost functions ⋮ Interpolation in Valiant's theory ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ A complex analogue of Toda's theorem ⋮ Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz ⋮ Unnamed Item ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Semidefinite programming and arithmetic circuit evaluation ⋮ Generic hardness of inversion on ring and its relation to self-bilinear map ⋮ Algebraic independence in positive characteristic: A $p$-adic calculus ⋮ On the ultimate complexity of factorials ⋮ Calculs sur les structures de langage dénombrable ⋮ Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\) ⋮ Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative? ⋮ Mathematical problems for the next century ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Bounds for the degrees in the Nullstellensatz
• On the intrinsic complexity of elimination theory
• Separation of complexity classes in Koiran's weak model
• On asymptotic estimates for arithmetic cost functions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The cost of computing integers
• Unnamed Item
• Unnamed Item

This page was built for publication: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?