On self-reducibility and weak P-selectivity

摘要

Self-reducible sets and some low sets, including p-selective sets, and weakly p-selective sets are studied. Several different formulations of self-reducible sets are given and compared with each other. A new characterization of p-selective sets is found, and weakly p-selective sets are introduced as a generalization of p-selective sets based on this characterization. It is proved that self-reducible sets are not polynomial-time Turing reducible to these sets. As a consequence, ⩽pm-completeness and ⩽pT-completeness in NP are not likely to be distinguished by weakly p-selective sets.