scientific article; zbMATH DE number 503394

MaRDI QIDQ4279733zbMATH OpenFDO

Authors Nimrod Megiddo

Publication date 22 February 1994

zbMATH Keywords

computations over a general ringCook's NP-completeness

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4131650
• A note on a theorem of Blum, Shub, and Smale
• Relativizations of the P=?NP question over the reals (and other ordered rings)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Structure of $\cal NP_\Bbb C$

Cited in

(6)

• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• On NP-completeness for linear machines
• scientific article; zbMATH DE number 3963808 (Why is no real title available?)
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• Computability of String Functions Over Algebraic Structures Armin Hemmerling
• scientific article; zbMATH DE number 958366 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4279733)