On the Structure of \cal NP_\Bbb C

DOI10.1137/S0097539795294980MaRDI QIDQ4210134zbMATH OpenFDO

Authors Gregorio Malajovich, Klaus Meer

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

complexityNP-completenessHilbert NullstellensatzBSS machines over \(\mathbb C\)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Relativizations of the P = NP problem over the complex number field
• A note on non-complete problems in \(NP_\mathbb{R}\)
• Topics in real and complex number complexity theory
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)

Cited in

(12)

• On Ladner's result for a class of real machines with restricted use of constants
• Saturation and stability in the theory of computation over the reals
• On Ladner's result for a class of real machines with restricted use of constants
• \(\text{NP}\not={co}\)-NP and models of arithmetic
• scientific article; zbMATH DE number 3999295 (Why is no real title available?)
• Some initial thoughts on bounded query computations over the reals
• Some aspects of studying an optimization or decision problem in different computational models
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• A note on non-complete problems in \(NP_\mathbb{R}\)
• The P\(\neq\) NP conjecture in the context of real and complex analysis
• An explicit solution to Post's problem over the reals
• Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines

This page was built for publication: On the Structure of $\cal NP_\Bbb C$

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