![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
![]() |
Однако не известно, совпадают ли классы P и NP, но большинство специалистов считает, что нет. Интуитивно класс Р можно представить себе как класс задач, которые можно быстро решить, а класс NP – как класс задач, решение которых можно быстро проверить.
Существуют и другие открытые вопросы относительно класса NP:
1. Вопрос эквивалентности классов P и NP.
2. Вопрос замкнутости класса NP относительно дополнения, т. е. верно ли, что если L NP, то и
NP. Множество всех задач L, для которых это условие выполняется, назовем классом co-NP.
Так как класс Р замкнут относительно дополнения, то возможны следующие соотношения классов.
Дата публикования: 2015-07-22; Прочитано: 503 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!