Title :
Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles
Author :
Vereschchagin, N.K.
Author_Institution :
Inst. of New Technol., Moscow
Abstract :
It is proved that relative to random oracle A (with respect to the uniform measure) the following assertions hold: (1) there is a pair of disjoint NPA-sets that are separable by no PA-set, (2) there is a pair of disjoint Co-NPA-sets that are separable by no PA-set, and (3) there is an infinite Co-NPA-set having no infinite NPA-subset
Keywords :
computational complexity; Co-NP-sets; NP-sets; P-sets; disjoint NPA-sets; random oracles; Complexity theory;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336533
