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

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

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

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

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

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

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