P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
From MaRDI portal
Publication:1338220
DOI10.1016/0304-3975(94)00067-0zbMath0822.68033OpenAlexW2050813033MaRDI QIDQ1338220
Publication date: 9 October 1995
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00067-0
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Nonstandard arithmetic and field theory (12L15)
Related Items (8)
Two situations with unit-cost: ordered abelian semi-groups and some commutative rings ⋮ On Ladner's result for a class of real machines with restricted use of constants ⋮ A note on non-complete problems in \(NP_\mathbb{R}\) ⋮ On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants ⋮ On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture ⋮ Calculs sur les structures de langage dénombrable ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Saturation and stability in the theory of computation over the reals
Cites Work
- Unnamed Item
- Unnamed Item
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Model theory.
- Alfred Tarski's elimination theory for real closed fields
- Algorithmic Procedures
- An introduction to recursively saturated and resplendent models
- Accessible telephone directories
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
This page was built for publication: P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
