Математическая логика и теория алгоритмов. Стенюшкина В.А. - 73 стр.

язык L1 сводится к языку L2, если существует такая функция f:  0,1
*→0,1*, что для любого x ∈0,1* свойства x ∈ L1 и f(х) ∈ L2 эквивалентны.
Функция f называется сводящей функцией, а алгоритм, вычисляющий функцию
f, – сводящим алгоритмом. Если функция f вычислима за полиномиальное вре-
мя, то говорят, что язык L1 сводится к языку L2 за полиномиальное время и
используют запись: L1 ≤ р L2. Сводящая функция переводит любое слово x ∈
L1 в слово f(х) ∈ L2, а слово х ∉ L1 – в слово f(х) ∉ L2. Поэтому по ответу на
вопрос: «f(х) ∈ 2?» мы получаем ответ на вопрос «х ∈ L1?». Справедливо
утверждение: Если языки L1, L2 ⊂  0,1*, и L1 ≤ р L2, то из L2 ∈ Р следует,
что L1∈ Р. При этом запись L1 ≤ р L2 можно интерпретировать так, что слож-
ность языка L1 не более чем полиномиально превосходит сложность языка L2.
       Основное определение Язык L1⊂ 0, 1* называется NP – полным, если
выполняются условия:
       1)   L1∈ NP;
       2)   для любого L2 ∈ NP выполняется отношение L2 ≤ р L1.
       Язык L1⊂ 0,1* называется NP – трудным, если выполнено условие 2), а
условие 1) может выполняться или не выполняться.
       Основная теорема Если некоторая NP – полная задача разрешима за по-
линомиальное время, то Р = NP. Иначе говоря, если в классе NP есть задача, не
разрешимая за полиномиальное время, то все NP – полные задачи таковы.
       Доказательство Если некоторый язык L1 является NP – полным и в то же
время разрешимым за полиномиальное время, то для любого языка L2 ∈ NP из
свойства 2) основного определения следует, что L2 ≤р L1. Последнее означает,
что L2∈Р. Утверждение в первой формулировке доказано. Вторая формулиров-
ка теоремы эквивалентна первой. В соответствии с этой теоремой предположе-
ние о том, что Р ≠ NP означает, что NP – полные задачи не могут быть решены
за полиномиальное время. Пока никто не предъявил полиномиальный алгоритм
для решения NP – полной задачи, и никто не доказал N ≠ NP.


                      3.6.6 Примеры NP – полных задач

       Имеется множество NP – полных задач в различных разделах математи-
ки: логике, графах, алгебре и так далее. Рассмотрим несколько примеров.
       1 Задача о выполнимости схемы Дана схема, состоящая из элементов «и»,
«или», «не». Требуется выяснить, является ли эта схема выполнимой. При этом
схема из функциональных элементов с несколькими входами и одним выходом
называется выполнимой, если существует входной булев вектор, для которого
выходной скаляр есть единица. Как уже известно, эта задача сводится к задаче
о выполнимости пропозициональной формулы ϕ ≡ ((х1→х2) ∨  ((х1 ↔ х3) ∨ х4
)) ∧  х2 имеет выполняющий набор (х1, х2, х3, х4) = (0, 0, 1, 1). (проверьте!) Вы-
полнимость можно проверить, перебрав все наборы значений переменных (для
формулы с n переменными их 2n). В данном случае достаточно проверку прове-
сти для представленного образца. Переборный алгоритм как видно, не является