A Note on Non-complete Problems in NP[formula omitted]

This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2000-03, Vol.16 (1), p.324-332
Main Authors: Ben-David, S., Meer, K., Michaux, C.
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/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).
ISSN:0885-064X
1090-2708
DOI:10.1006/jcom.1999.0537