scientific article

zbMath0691.68034MaRDI QIDQ3033315

Michael Shub, Lenore Blum, Stephen Smale

Publication date: 1990

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-complete problemscomputable functionspartial recursive functionsCook's theoremmachines over a ring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80) Turing machines and related notions (03D10)

Related Items (12)

Two situations with unit-cost: ordered abelian semi-groups and some commutative rings ⋮ On genuinely time bounded computations ⋮ Strong time bounds: Non-computable bounds and a hierarchy theorem ⋮ A note on a theorem of Blum, Shub, and Smale ⋮ Computations over \(\mathbb{Z}\) and \(\mathbb{R}\): a comparison ⋮ Computing the partition function of the Sherrington-Kirkpatrick model is hard on average ⋮ On the decidability of sparse univariate polynomial interpolation ⋮ On the computational complexity of integral equations ⋮ \(\text{P}\neq \text{NP}\) for the reals with various analytic functions ⋮ On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture ⋮ The Irrationals are not Recursively Enumerable ⋮ Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space

This page was built for publication: