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)

Full work available at URL https://doi.org/10.1137/S0097539795294980

zbMATH Keywords

BSS machines over \(\mathbb C\)complexityHilbert NullstellensatzNP-completeness

Mathematics Subject Classification ID

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

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

(14)

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

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)