✦ LIBER ✦

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

✍ Scribed by Harry Buhrman; Leen Torenvliet

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 361 KB
Volume: 53
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1996.0062

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

P-Selective Sets and Reducing Search to

P-Selective Sets and Reducing Search to Decision vs Self-Reducibility

✍ Edith Hemaspaandra; Ashish V. Naik; Mitsunori Ogihara; Alan L. Selman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 684 KB

We distinguish self-reducibility of a language L with the question of whether search reduces to decision for L. Results include: (i) If NE{E, then there exists a set L in NP&P such that search reduces to decision for L, search does not nonadaptively reduce to decision for L and L is not self-reducib

On polynomial-time truth-table reducibil

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

✍ Seinosuke Toda 📂 Article 📅 1991 🏛 Springer 🌐 English ⚖ 739 KB

Reductibility classes of P-selective set

Reductibility classes of P-selective sets

✍ Lane A. Hemaspaandra; Albrecht Hoene; Mitsunori Ogihara 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 807 KB

P-selective sets, tally languages, and t

P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

✍ Alan L. Selman 📂 Article 📅 1979 🏛 Springer 🌐 English ⚖ 677 KB

A characterization of semilinear sets

✍ L.Y. Liu; P. Weiner 📂 Article 📅 1970 🏛 Elsevier Science 🌐 English ⚖ 372 KB

In this report, the class of semilinear sets is shown to be the least class of sets which contains all of the stratified semilinear sets and is closed under finite intersection.

A New Characterization of NP, P, and PSP

A New Characterization of NP, P, and PSPACE with

✍ Florin Manea; Maurice Margenstern; Victor Mitrana; Mario J. Pérez-Jiménez 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 425 KB