๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Reductibility classes of P-selective sets

โœ Scribed by Lane A. Hemaspaandra; Albrecht Hoene; Mitsunori Ogihara


Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
807 KB
Volume
155
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


Taxonomic classes of sets
โœ James F Lynch ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 387 KB
Donsker classes of sets
โœ Michel Talagrand ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Springer ๐ŸŒ English โš– 999 KB
P-Selective Self-Reducible Sets: A New C
โœ Harry Buhrman; Leen Torenvliet ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 361 KB

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 a