P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)

DOI10.1016/0304-3975(94)00067-0zbMath0822.68033OpenAlexW2050813033MaRDI QIDQ1338220

Christian Michaux

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

zbMATH Keywords

NP-complete problem

Mathematics Subject Classification ID

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