A NOTE ON NON-COMPLETE PROBLEMS IN N_{R}

S. BEN-DAVID K. MEER C. MICHAUX

Abstract. This note deals with the structure of the class N_{R} introduced by Blum, Shub and Smale. It is shown that, assuming N_{R} is not included in the class P_{R}/poly , there exists a problem in N_{R} which does not belong to P_{R}/poly and which is not N_{R}-complete. It also clarifies the scope of a padding technique used in a former similar result by Ladner concerning the structure of the class NP (in the common, Turing machine, model).