ВУЗ:
Составители:
Таким образом, гипотеза P ≠ NP означает, что NP-полные задачи не могут быть
решены за полиномиальное время. Большинство экспертов полагают, что это
действительно так; предполагаемое соотношение между классами P, NP и NPC показано
на рис. 3.
Конечно, мы не можем быть уверены, что однажды кто-нибудь не предъявит
полиномиальный алгоритм
для решения NP-полной задачи и не докажет тем самым, что
P=NP. Но пока этого никому не удалось, и поэтому доказательство NP-полноты
некоторой задачи является убедительным аргументом в пользу того, что она является
практически неразрешимой.
NP
NPC
P
Рис. 3. Предполагаемое соотношение между классами P, NP и NPC.
Классы P и
NPC содержатся в NP (что очевидно), и, можно полагать, не пересекаются и
не покрывают всего NP.
Первой задачей, для которой была доказана её NP-полнота была задача о
выполнимости пропозициональных формул:
SAT = {<ϕ>: ϕ – пропозициональная и выполнимая формула}.
В неформальной постановке:
Условие. Дана формула исчисления высказываний ϕ.
Вопрос. Существует ли
такое распределение истинностных значений
высказывательных переменных, при которых формула ϕ выполнима?
Теорема 42(теорема Кука). Задача SAT является NP-полной [10, с.56–63].
Можно сказать так: после доказательства этой теоремы была пробита брешь в
стене и установлена NP-полнота одной задачи, после этого было доказано с помощью
сводимости NP-полнота большого числа задач [10, 13]. В
разделе 6.3 мы перечислили
некоторые задачи, которые не попадают ни в класс P, ни в класс E. Все они являются NP-
полными.
Забудь, что прочел.
Учись читать заново.
Так сказал сэнсэй.
Б. Акунин
Алмазная колесница
