Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Нерешенные проблемы теории NP-полноты



 
 

Как соотносятся классы P и NP? Так как любая задача класса Р проверяема за полиномиальное время, то очевидно следующее включение.

Однако не известно, совпадают ли классы P и NP, но большинство специалистов считает, что нет. Интуитивно класс Р можно представить себе как класс задач, которые можно быстро решить, а класс NP – как класс задач, решение которых можно быстро проверить.

Существуют и другие открытые вопросы относительно класса NP:

1. Вопрос эквивалентности классов P и NP.

2. Вопрос замкнутости класса NP относительно дополнения, т. е. верно ли, что если L NP, то и NP. Множество всех задач L, для которых это условие выполняется, назовем классом co-NP.

Так как класс Р замкнут относительно дополнения, то возможны следующие соотношения классов.






Дата публикования: 2015-07-22; Прочитано: 503 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...