P-Selective Self-Reducible Sets: A New Characterization of P

摘要

We show that any p-selective and self-reducible set is in P. As the converse is also true, we obtain a new characterization of the class P. A generalization and several consequences of this theorem are discussed. Among other consequences, we show that under reasonable assumptions auto-reducibility and self-reducibility differ on NP, and that there are non-p-T-mitotic sets in NP.