|
NeuroCOLT
Technical Report NC-TR-97-007
A
Note on Non-complete Problems in NPR
S.
Ben-David, Technion
Israel
K.
Meer
RWTH, Aachen
Germany
C.
Michaux
Universite de Mons-Hainaut
Belgium
Abstract
This note deals with the structure of the class $NP_{\Re}$
introduced by Blum, Shub and Smale \cite{BSS}. It is shown that, assuming
$NP_{\Re} \not\subseteq $P_{\Re} /poly$, there exists a problem in
$NP_{\Re} \setminus (P_{\Re} /poly)$ which is not $NP_{\Re}$-complete
(w.r.t $P_{\Re} /poly$ reductions). It also clarifies the scope of
padding technique used in a former similar result by Ladner \cite{La}
concerning the structure of the class $NP$ (in the common, Turing
machine, model).
Download Compressed Postscript
|