|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Relationships between NP-sets, coNP-sets and P-sets relative to random oraclesстатья
Информация о цитировании статьи получена из
Web of Science
Дата последнего поиска статьи во внешних источниках: 27 мая 2015 г.
- Автор: Vereshchagin N.
- Сборник: Proc. 8th Conference on Structure in Complexity Theory
- Год издания: 1993
- Издательство: IEEE Computer Society Press
- Местоположение издательства: Los Alamitos, CA, United States
- Первая страница: 132
- Последняя страница: 138
- DOI: 10.1109/SCT.1993.336533
- Аннотация: 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 NP^A-sets that are separable by no P^A-set, (2) there is a pair of disjoint Co-NP^A-sets that are separable by no P^A-set, and (3) there is an infinite Co-NP^A-set having no infinite NP^A-subset.
- Добавил в систему: Верещагин Николай Константинович