NP – полнота и сводимость

Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование NP - полных задач. Это самые труднорешаемые задачи в классе NP. Для их решения используются недетерминированные машины Тьюринга с полиномиальным временем работы на ветвях, где они допускают данный вход. Недетерминирован- ная машина имеет возможность угадывать экспоненциальное число решений проблемы и параллельно проверять каждое из них (за полиномиальное время).

Понятие полиномиальной сводимости позволяет придать точный смысл тому, что одна проблема не менее сложна, чем другая.

Язык L Í {0,1}^* называется NP – полным, если 1) L Î NP и

2) для любого L^’ Î NP : L^’ £ _P L .

Теорема. Если некоторая NP – полная задача разрешима за полиномиальное время, то P = NP. Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP – полные задачи не разрешимы за полиномиальное время.

Доказательство. Пусть L - NP – полный язык разрешимый за полиномиальное время. По свойству 2, для любого языка L^’ Î NP : L^’ £ _P L .

Тогда по лемме, L^’ Î P, так что P = NP.

Если некоторый язык L^’ Î NP не разрешим за полиномиальное время, и так как любой язык из класса NP полиномиально сводим к NP – полному языку L, то L не разрешим за полиномиальное время. Иначе по первой части теоремы, L^’ разрешим за полиномиальное время, что противоречит условию. “

Таким образом, гипотеза P ¹ NP означает, что NP – полные задачи не могут быть решены за полиномиальное время на детерминированной машине Тьюринга.