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

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, 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