A Note on Non-complete Problems in NPImage
Abstract This note deals with the structure of the class NP R introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NP R ⊈P R /poly, there exists a problem NP R \(P R /poly) which is not NP R -complete (w.r.t P R /poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, J. Assoc. Comput. Mach.22, 155–171) concerning the structure of the class NP (in the common, Turing machine, model).