Математическая теория формальных языков
Классы P и NP
Определение 15.8.1.
Пусть машина Тьюринга M допускает язык L. Говорят, что язык L распознается за полиномиальное время на машине M, если существует такой многочлен p, что любое слово
принимается машиной M не более чем за p(|w|) тактов.
Определение 15.8.2.
Через P обозначается класс тех языков, которые распознаются за полиномиальное время на некоторой детерминированной машине Тьюринга.
Определение 15.8.3.
Через NP обозначается класс тех формальных языков, которые распознаются за полиномиальное время на некоторой (в общем случае недетерминированной) машине Тьюринга.
Замечание 15.8.4.
Очевидно, что . Неизвестно, совпадают ли классы P и NP.
Теорема 15.8.5.
Все языки из класса NP являются разрешимыми.
Определение 15.8.6.
Всюду определенная функция f из
в
называется вычислимой за полиномиальное время, если ее вычисляет некоторая детерминированная машина Тьюринга M (если , то данная функция f рассматривается как частичная функция из
в ) и существует такой многочлен p, что для любого слова
машина M вычисляет значение f(w) не более чем за p(|w|) тактов.
Определение 15.8.7.
Язык
полиномиально сводится (is polynomial time reducible) к языку , если существует такая вычислимая за полиномиальное время всюду определенная функция f из
в , что для любого слова
условие
равносильно условию .
Определение 15.8.8.
Формальный язык L называется NP-сложным (NP-hard}, если каждый язык из класса NP полиномиально сводится к языку L.
Определение 15.8.9.
Формальный язык называется NP-полным (NP-complete), если он принадлежит классу NP и является NP-сложным.
Определение 15.8.10.
Алгоритмическая проблема, относящаяся к некоторой задаче распознавания, называется NP-полной, если множество кодов индивидуальных задач с ответом "да" является NP-полным языком.
Теорема 15.8.11 (теорема Кука-Левина).
Проблема выполнимости булевых формул в конъюнктивной нормальной форме N-полна.
Доказательство можно найти, например, в [Сэв, с. 325-328] или [ГэрДжо, с. 57-63].
Упражнение 15.8.12.
Существует ли такой язык
из класса P, что язык не принадлежит классу P?
Упражнение 15.8.13.
Существуют ли такие языки L1 и L2
из класса P, что язык
не принадлежит классу P?
Упражнение 15.8.14.
Существуют ли такие языки L1 и L2
из класса NP, что язык
не принадлежит классу NP?
