|
NeuroCOLT
Technical Report NC-TR-95-037
P
\neq NP over the non standard reals
implies P \neq NP over R
Christian
Michaux
University of Mons-Hainaut
Belgium
Abstract
Blum, Shub and Smale showed the existence of a $\NP$-complete
problem over the real closed fields in the framework of their theory
of computation over the reals. This allows to ask for the $\P\neq
\NP$ question over real closed fields. Here we show that $\P\neq\NP$
over a real closed extension of the reals implies $\P\neq \NP$ over
the reals. We also discuss the converse. This leads to define some
subclasses of $\P/$poly. Finally we show that the transfer result
about $\P\neq \NP$ is a part of a very abstract result.
Download Compressed
Postscript
|