A note on non-complete problems in NP_R
From MaRDI portal
Publication:1977151
DOI10.1006/JCOM.1999.0537zbMATH Open0953.68058OpenAlexW2044150078MaRDI QIDQ1977151FDOQ1977151
Authors: Yanyan Li 
Publication date: 22 June 2000
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcom.1999.0537
Recommendations
Cites Work
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the Structure of Polynomial Time Reducibility
- 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}\)
- On the Structure of $\cal NP_\Bbb C$
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Two \(P\)-complete problems in the theory of the reals
- Accessible telephone directories
- A uniform approach to obtain diagonal sets in complexity classes
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (9)
- On Some $\mathcal{NP}$ -complete SEFE Problems
- 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
- On Unapproximable Versions of $NP$-Complete Problems
- On strong NP-completeness of rational problems
- P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
- An explicit solution to Post's problem over the reals
- Some aspects of studying an optimization or decision problem in different computational models
This page was built for publication: A note on non-complete problems in \(NP_\mathbb{R}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1977151)
