1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 24
Текст из файла (страница 24)
Пусть T = hA, Q, P, q1 , q0 i — детерминированная машина Тьюрингаи задан некоторый алфавит A0 ⊆ A \ {0}. Говорят, что машина T вычисляет всюдуопределенную словарную функцию f : A∗0 → A∗0 , если для любого слова w ∈ A∗0имеет местоq1 0w0 =⇒ q0 0f (w)00s , для некоторого s > 0.TДругими словами, машина T на входе q1 0w0 всегда останавливается, преобразуяначальную конфигурацию без достраивания новых ячеек слева в конфигурациюq0 0f (w)00 . . . 0.Функция f : A∗0 → A∗0 называется полиномиально вычислимой, если существуетполиномиально ограниченная над алфавитом A0 детерминированная машина Тьюринга, которая вычисляет f .Замечание.
Для всюду определенных функций вида f : ω → ω предыдущее определение согласуется со старым определением вычислимой по Тьюрингу частичнойфункции. При этом мы, как обычно, заменяем числовую функцию f : ω → ω на еесловарный аналог f : {1}∗ → {1}∗ по правилу f (1n ) = 1f (n) и рассматриваем машиныТьюринга над алфавитом A = {0, 1}.Таким образом, любая полиномиально вычислимая функция f : ω → ω обязана быть частично вычислимой. Возникает естественный вопрос: существуют личастично вычислимые функции, которые не вычислимы полиномиально? Интуитивные рассуждения, приведенные во введении в данную главу, дают нам основаниядля утвердительного ответа на этот вопрос. Ниже мы дадим более формальное доказательство этого факта.Теорема 78.
Существует двухместная вычислимая функция F (n, x), универсальная для семейства {f : ω → ω | f — полиномиально вычислима}.Доказательство. Мы изложим только идею доказательства. Пусть pm (x) — универсальная вычислимая функция для семейства всех полиномов с натуральнымикоэффициентами (см. предложение 65).Неформальный алгоритм для вычисления функции F (n, x) имеет следующее описание.
Запускаем машину Тьюринга с номером (n)0 на входной конфигурации q1 01x 0и проделываем ровно p(n)1 (x) шагов работы машины. Если за данное количествошагов вычисление успешно завершилось, т. е. машина перешла без достраивания новых ячеек слева в конфигурацию вида q0 01y 0 . . . 0, то выдаем y в качестве значенияF (n, x). В противном случае выдаем 0.Определенная подобным образом функция F является искомой.98Глава V.
Теория сложности алгоритмовСледствие 79. Существует вычислимая функция, не являющаяся полиномиальновычислимой.Доказательство. Допустим, напротив, любая вычислимая функция вида f : ω → ωполиномиально вычислима. Следовательно, семейство всех одноместных вычислимых функций совпадает с семейством {f : ω → ω | f — полиномиально вычислима}.Тогда вычислимая функция F (n, x), построенная в теореме 78, будет универсальной для семейства всех одноместных вычислимых функций. Последнее противоречитпредложению 62.Определение.
Говорят, что язык L1 ⊆ A∗0 полиномиально сводится к языку L2 ⊆A∗0 , если существует полиномиально вычислимая словарная функция f : A∗0 → A∗0 ,такая, что для любого слова w ∈ A∗0 выполняется:w ∈ L1 ⇐⇒ f (w) ∈ L2 .В теории сложности традиционно языки отождествляют с проблемами вхождения слов в эти языки. В данной терминологии полиномиальная сводимость языка L1к языку L2 означает, что проблема L1 не сложнее, чем проблема L2 .
Если существуетдетерминированная машина, разрешающая проблему L2 за полиномиальное время,то ее можно эффективно преобразовать в детерминированную машину, которая разрешает проблему L2 также за полиномиальное время.Определение. Язык L0 ⊆ A∗0 называется NP-полным, если L0 ∈ NP и любой языкL ∈ NP полиномиально сводится к L0 .Из определения следует, что все NP-полные языки сводятся друг к другу. Семейство NP-полных языков играет очень важную роль в теории сложности. Если хотябы для одной из NP-полных проблем удастся найти детерминированный алгоритм,решающий эту проблему за полиномиальное время, то будет справедливо равенствоP = NP, и все остальные проблемы из этого семейства также будут решаться с помощью детерминированных полиномиальных алгоритмов.Теорема 80.
Пусть L — произвольный NP-полный язык. Равенство P = NP выполняется тогда и только тогда, когда L ∈ P.Доказательство. Докажем сначала необходимость. Пусть P = NP. Из определенияNP-полноты вытекает, что L ∈ NP. Следовательно, L ∈ P.Теперь докажем достаточность. Пусть L ∈ P. Следовательно, найдется детерминированная машина Тьюринга T1 , полиномиально ограниченная полиномом p1 (n),которая распознает L. Пусть далее L0 — произвольный язык из класса NP. Требуется показать, что L0 ∈ P.В силу NP-полноты языка L язык L0 полиномиально сводится к L посредствомнекоторой полиномиально вычислимой функции f .
Следовательно, существует детерминированная машина Тьюринга T2 , полиномиально ограниченная полиномомp2 (n), которая вычисляет f .Рассмотрим композицию машин T2 T1 . Очевидно, что T2 T1 является детерминированной машиной. Машина T2 T1 распознает слово w тогда и только тогда, когдаf (w) ∈ L. Условие f (w) ∈ L, в свою очередь, эквивалентно условию w ∈ L0 . Такимобразом, T2 T1 в точности распознает язык L0 .§ 27. Теорема Кука99Докажем, наконец, что машина T2 T1 полиномиально ограничена.
Работа машиныT2 T1 на произвольном входном слове w состоит из двух этапов. На первом этапемашина T2 перерабатывает w в слово f (w) за не более, чем p2 (|w|) шагов. Посколькумашина T2 за один такт работы способна записать на ленту не более одного символа,то длина слова f (w) не превосходит p2 (|w|) + |w|. Следовательно, на втором этапемашина T1 перерабатывает слово f (w) в определенное выходное слово за не более,чем p1 (p2 (|w|) + |w|) шагов. Суммируя все подсчеты, заключаем, что машина T2 T1останавливается на входе w за не более, чем p2 (|w|) + p1 (p2 (|w|) + |w|) шагов, чтоявляется полиномом от |w|.§ 27.Теорема КукаВ предыдущем параграфе мы ввели понятие NP-полного языка, но мы до сих порне доказали, что такие языки существует.
Теперь нам предстоит восполнить этотпробел. На самом деле, в настоящее время известно достаточно много NP-полныхпроблем, которые имеют важное практическое значение и которые возникают в таких областях математики, как исследование операций, логика, комбинаторика, искусственный интеллект и др. Мы остановимся на проблеме выполнимости булевыхформул и докажем ее NP-полноту.Определение.
Пусть V = {Pi | i ∈ ω} — произвольное счетное множество, элементы которого мы будем называть пропозициональными переменными. Определимпонятие булевой формулы от пропозициональных переменных из V следующим образом по индукции:1) Любая пропозициональная переменная Pi является булевой формулой.2) Если Φ и Ψ — булевы формулы, то слова (Φ&Ψ), (Φ ∨ Ψ), ¬Φ также являютсябулевыми формулами.Замечание. Мы считаем, что символы &, ∨, ¬, (, ) не являются элементами множества V .
Таким образом, любая булева формула — это конечное слово в бесконечномалфавите V ∪ {&, ∨, ¬, (, )}. Будем считать, что булева формула Φ зависит от конечного списка переменных {Pi1 , . . . , Pin }, если любая пропозициональная переменная,имеющая вхождение в слове Φ, является элементом множества {Pi1 , . . . , Pin }.Определение. Пусть γ : V → {0, 1} — произвольное отображение из множествапропозициональных переменных V в двухэлементное множество {0, 1}, которое мыбудем называть означиванием переменных. Определим по индукции значение γ(Φ)булевой формулы Φ при означивании γ:1) Если Φ = Pi — пропозициональная переменная, то γ(Φ) = γ(Pi ).2) Если Φ = (Ψ&Θ), или Φ = (Ψ∨Θ), или Φ = ¬Ψ для некоторых булевых формулΨ, Θ, то значение γ(Φ) определяется в соответствии со следующей таблицей:γ(Ψ) γ(Θ)00011011γ(Ψ&Θ)0001γ(Ψ ∨ Θ)0111γ(¬Ψ)1100Булева формула Φ называется выполнимой, если существует хотя бы одно означивание переменных γ : V → {0, 1}, для которого γ(Φ) = 1.100Глава V.
Теория сложности алгоритмовЗамечание. Если булева формула Φ зависит от переменных {Pi1 , . . . , Pin }, то, очевидно, значения переменных, не входящих в этот конечный список, никак не влияютна значение формулы Φ. Таким образом, для того, чтобы определить, является лиданная формула Φ выполнимой, достаточно перебрать всевозможные наборы значений n переменных Pi1 , . . . , Pin (таких наборов будет 2n ) и для каждого такого наборавычислить значение формулы. Если среди полученных значений найдется хотя быодно значение 1, то Φ выполнима, в противном случае — невыполнима.Замечание. Как было замечено выше, множество всех булевых формул — это языкв некотором бесконечном алфавите.
Однако любая машина Тьюринга обладает лишьконечным внешним алфавитом. Поэтому для того, чтобы обработка булевых формулстала возможной на машинах Тьюринга, нам необходимо представить множествовсех формул как язык над конечным алфавитом.Примем следующие соглашение: булевы формулы будем представлять в видеслов над конечным алфавитом {0, 1, . . . , 9, &, ∨, ¬, (, )}, в которых каждая пропозициональная переменная Pi представляется десятичной записью числа i. При этомсимволы &, ∨, ¬, (, ) остаются в представлениях формул без изменений.Например, формула ¬(P13 &(P2 ∨ ¬P5 )) представляется словом ¬(13&(2 ∨ ¬5)).Всюду далее язык, образованный всеми словами, представляющими выполнимыебулевы формулы, будем называть проблемой выполнимости булевых формул.Определение. Пусть f (n) и g(n) — произвольные всюду определенные функции наω.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
