4. Теория сложности

До сих пор мы делили проблемы в общих чертах на разрешимые и не­­разрешимые. Теперь мы рассмотрим разрешимые проблемы с точки зрения их сложности. При этом сложность означает затраты ресурсов (времени, памяти и т.д.), которые расходуются для решения задачи в зависимости от ее объема.

Мы рассматриваем фиксированный класс детерминированных машин Тьюринга (односторонних – двусторонних, одноленточных – многолен­точных), которые завершают работу при любом входном слове. Пусть T машина Тьюринга с входным алфавитом  из этого класса. Функция time_T: ^  определяет количество шагов вычисления time_T(w), которое требуется машине T для обработки входного слова w^ вплоть до завер­шения работы. Класс TIME(f), где f:    – отображение, состоит из всех формальных языков L, которые могут приниматься (детерминированной) машиной Тьюринга T из рассмотренного класса, при time_T (w)  f (w), w^*.

Определим теперь класс формальных языков, которые могут быть при­няты в полиномиальное время:

P =.

При этом безразлично, какой класс детерминированных машин Тью­ринга мы используем. Если язык может быть принят за полиномиальное время с помощью двусторонней детерминированной машины Тьюринга T₁ с несколькими лентами, то и он может быть принят также в полиномиаль­ное время с помощью односторонней детерминированной машины Тью­ринга T₂ с одной лентой (машина T₂ требует, в общем случае, больше ша­гов вычисления, чем T₁).

Распространим теперь эти определения на фиксированные классы не­детерминированных машин Тьюринга, причем мы также допускаем, что рассмотренные машины Тьюринга завершают работу не для всех входных данных. Функция time_T: ^*  теперь измеряет минимальное количество шагов вычисления time_T (w), которое требуется машине Тьюринга T для входного слова w^*. В случае, если машина Тьюринга T для w^*не мо­жет завершить расчет, мы полагаем, time_T (w) = 0. Класс NTIME (f), где f:  – отображение, снова состоит из всех формальных языков L, кото­рые могут приниматься (недетерминированной) машиной Тьюринга T из рассмотренного класса, при time_T (w)  f (w), w^*.

Определим теперь класс формальных языков, которые могут прини­маться за недетерминированное полиномиальное время:

NP = .

Ясно, что выполняется P  NP. Неизвестно, однако, является ли это вклю­­чение правильным? Эта проблема называется проблемой P = NP и часто рас­сматривается как важнейший открытый вопрос теоретической инфор­матики.

Пусть L, L’  ^* – формальные языки. Тогда L’ называют полиноми­ально сводимым на L и обозначают L’  L, тогда и только тогда, если су­ществует тотальная и за полиномиальное время вычислимая с помощью детерминированной машины Тьюринга функция q: ^*  ^*, такая, что для всех w^* справедливо:

wL’  q (w)L

Очевидно, справедлив следующий результат:

Из L’  L и L  P (соответственно L  NP) следует также L’  P (со­ответственно L’ NP).

Формальный язык L называется NP-трудным тогда и только тогда, ко­гда все языки L’ NP можно полиномиально свести к L, то есть если для всех L’ NP справедливо: L’  L. Формальный язык L называется NP‑пол­ным тогда и только тогда, когда он лежит в NP и является NP‑трудным.

Предложение 4.1. Пусть L является NP-полным. Тогда имеет место:

L  P  P  NP 

Доказательство. Пусть L  P и L’ NP. Так как язык L NP-трудный, то имеет место L’  L. Из этого следует, что L’ P. Так как L’ был выбран произвольно, то, следовательно, P = NP. 

Таким образом, каждому для доказательства того, что P = NP следует показать, что его «излюбленная» NP-полная «проблема» лежит в P. Первой сложностью является, конечно, нахождение какой-либо NP-полной про­блемы. Мы покажем, что проблема выполнимости в логике высказываний («Является ли данная формула логики высказываний выполнимой?») явля­ется NP-полной. Для формализации этой проблемы мы должны кодировать атомарные формулы и вместе с тем множество всех формул логики выска­зываний. Тем самым мы определяем формальный язык SAT всех выполни­мых формул логики высказываний.

Предложение 4.2. Язык SAT лежит в NP.

Доказательство. Недетерминированная машина Тьюринга T может распознать выполнимые формулы следующим образом: она устанавливает, какие атомарные формулы встречаются в формуле, недетерминированным образом предлагает одну подстановку для этих атомарных формул с буле­выми значениями (из множества 2^k возможных подстановок для k атомар­ных формул) и рассчитывает булевы значения формулы для выбранной подстановки. Теперь очевидно, что представленная формула лежит в SAT тогда и только тогда, когда, по крайней мере, одно из этих недетерминиро­ванных вычислений дает булево значение true. Каждое из этих вычисле­ний выполняется за полиномиальное время, так как количество атомарных формул не превышает длину заданной формулы. 

Доказательство предложения показывает кое-что очень характерное. Недетерминированная машина Тьюринга может рассматриваться как ме­ханизм, который проверяет данное предложение решения проблемы на предмет его корректности. Временная сложность недетерминированной машины Тьюринга может рассматриваться как затраты времени на то, чтобы там проверить предложение на корректность.

Предложение 4.3. Язык SAT является NP-трудным (и вместе с тем NP‑полным).

Доказательство. Пусть L лежит в NP. Тогда существует недетермини­рованная, полиномиально ограниченная по времени машина Тьюринга T, которая принимает L. Машина Тьюринга T обладает односторонней, по­тенциально бесконечной лентой, ячейки памяти которой пронумерованы как 0,1,2,.... Пусть она модифицирована таким образом, что головка чте­ния-записи также может оставаться стационарной и что если она достигает однажды заключительного состояния q, она в q остается, ничего не изме­няя: (q,A) = {q,A,S) для всех A. Пусть p – полином, ограничивающий время вычислений машины T. Через вышеупомянутые модификации мы достигаем, что любое вычисление машины T для входных данных длины n может быть прервано в точности после p(n) прямых переходов.

Пусть T = (Q,,,,q_o,F), где  = {e,Z_o,A₁,..,A_m} и Q = {q₀, q₁,…,q_k}. Для доказательства предложения мы будем для входного слова w^* конст­руировать формулу логики высказываний F (w), так что имеет место:

w  L  F (w) – выполнима.

Формула логики высказываний F(w), w = n содержит следующие ато­марные формулы:

(1) zust t,q], 0 t p n), qQ.

Замещение zust t,q] значением true означает, что машина T после t шагов находится в состоянии q.

(2) pos [t,i], 0 t p n); 0 i p(n).

Замещение pos [t,i] значением true означает, что головка чтения-записи T после t шагов находится в ячейке памяти i.

(3) band [t,i,A], 0 t p(n), 0 i p(n), A.

Замещение band [t,i,A] значением true означает, что после t шагов ячейка памяти i занята символом A.

Для доказательства мы используем формулу Gx₁,...,x_r, которая содержит атомарные формулы x₁,...,x_r и для которых имеет место:

G x₁,..., x_r  = true  для единственного i, 1 i r, x_i замещается на true.