On the Structure of \cal NP_\Bbb C

DOI10.1137/S0097539795294980zbMATH Open0915.68069MaRDI QIDQ4210134FDOQ4210134

Authors: Gregorio Malajovich, Klaus Meer 

Publication date: 21 September 1998

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

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}\)

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)

Cited In (12)

• Some initial thoughts on bounded query computations over the reals
• 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
• 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}\)
• A note on non-complete problems in \(NP_\mathbb{R}\)
• The P\(\neq\) NP conjecture in the context of real and complex analysis
• Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machines
• Title not available (Why is that?)
• An explicit solution to Post's problem over the reals
• \(\text{NP}\not={co}\)-NP and models of arithmetic
• Some aspects of studying an optimization or decision problem in different computational models

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)