Мы определяем ее через

G(x₁,...,x_r    x_i    x_i  x _j

Формула F (w) имеет следующую структуру:

F(w) = R  A  U₁  U₂  E.

При этом R описывает граничные условия, A – начальную конфигурацию, E – определенное заключительное условие и U₁, U₂ – определенные усло­вия перехода.

(i) R = R₁  R₂  R₃  с

R₁ = G (zust[ t,q₀ ,…,zust[t,q_k 

(к моменту времени t T находится точно в одном состоянии),

R₂ = G (pos[t,0],...,pos[t,p(n)])

(к моменту времени t головка чтения-записи машины T на­ходится точно в одной ячейке памяти),

R₃ = G (band[t,i,e], band[t,i,Z_o], band[t,i,A₁],…,band[t,i,A_m])

(к моменту времени t ячейка памяти i занята точно одним символом из ).

(ii) Пусть w = x₁,…,x_n, x_i. Тогда начальная конфигурация будет (в момент времени t = 0) описываться следующим образом:

A = zust[0,q₀]  pos[0,0] 

 band[0,0,Z_o]  band[0,i,x_i]   band[0,i,e].

(iii) E = zust[p(n),q].

Таким образом, условие E подтверждается, если машина T к мо­менту времени p(n) находилась в заключительном состоянии.

(iv) U₁ и U₂ описывают непосредственный переход T от момента вре­мени t к моменту времени t+1. При этом U₁ описывает ячейку па­мяти, над которой находится головка чтения-записи, в то время как U₂ описывает другие ячейки памяти.

U ₁ = zust[t,q]pos[t,i]band[t,i,A] 

(zust[t+1,p]  pos[t+1,i+D] band[t+1,i,B]),

при L= -1, R= +1 и S =0.

U₂ =  pos[t,i]  band[t,i,A]  band[t+1,i,A]).

Таким образом, существует точно одно замещение атомарных формул F(w), так что F(w) получает булево значение true, если R описывает после­­довательность из p(n)+1 конфигураций, которая представляет допустимое вы­числение (гарантируемое посредством U₁, U₂) от начальной конфигура­ции (описываемой через A) к принимающей конфигурации (описываемой через E).

Время вычисления T связано полиномиально с длиной формулы F(w). Так как F (w) содержит полиномиально много (в зависимости от w= n) атомарных формул, то булево значение F(w) может быть рассчитано в по­линомиальное время. 

Язык SAT представляет сам по себе чрезвычайно важную проблему для практической информатики. Факт NP-полноты языка SAT показывает, что при сегодняшнем состоянии знаний, для того чтобы установить выполни­мость формул логики высказываний, необходимо нереально большое время вычислений.

Формула логики высказываний лежит в формальном языке 3SAT (соответ­ственно 2SAT) тогда и только тогда, если она записана в конъюнктив­ной нор­мальной форме, и каждый дизъюнкт содержит не более трех (соот­ветственно двух) литералов. Через полиномиальную сводимость и также через доказатель­ство того, что SAT  3SAT, показывают, что 3SAT также является NP-полным.

В отличие от этого 2SAT лежит в P потому, что существует только по­линомиальное число различных дизъюнктов с двумя литералами, которые могут образовываться из атомарных формул x₁,...,x_n. Так как резольвента двух двухэлементных клаузелей снова является двухэлементной, тогда не­выполнимость или выполнимость формулы в конъюнктивной нормальной форме с не более чем с двумя литералами на дизъюнкт может быть под­тверждена в (детерминированное) полиномиальное время.

Теперь покажем полиномиальную сводимость языка 3SAT к проблеме теории графов СLIQUE. При этом пара (G, n), где G ненаправленный граф и n  , лежит в СLIQUE тогда и только тогда, когда G содержит клику (т.е. максимальный полный подграф) величины n.

Предложение 4.4. СLIQUE является NP-полной.

Доказательство. Для заданной пары (G, n) в полиномиальное время может быть недетерминировано выбрано n-элементное подмножество множества узлов G и затем может быть проверено, представляет ли оно клику. Тем самым СLIQUE  NP.

Теперь покажем, что СLIQUE является NP-трудной. Доказательство производится путем полиномиального сведения языка 3SAT к СLIQUE.

Пусть F – формула

(z₁₁  z₁₂  z₁₃) ...(z _{n 1} z _{n 2} z _{n 3}),

причем z_ij являются литералами над атомарными формулами x₁, x₂,... Этой формуле F сопоставляется теперь пара (G, n), где G граф, у которого

множество узлов V = {(i,j) | 1 i n, 1 j 3} и

множество ребер E = (i,j, (p,q)  i p, z_ij  z_pq }.

Тогда следующие высказывания равносильны:

F выполнима через подстановку  

в каждом дизъюнкте формулы F найдется литерал, который под дей­ствием  получает значение true (например, как ,,…,) 

Существуют литералы ,,…, так, что для pq справед­ливо:   

Существуют n узлов в G (например (1,j₁), (2,j₂),…,(n,j_n)), которые связаны попарно 

G содержит клику величины n.

Так как каждая формула в 3SAT тривиальным образом эквивалентна формуле F вида

(z₁₁  z₁₂  z₁₃) ... (z _n1 z _n2z _n3)

и пару (G, n) можно получить из F в полиномиальное время, то мы пока­зали тем самым, что СLIQUE является NP-трудной. 

Без доказательства укажем еще некоторые NP-трудные проблемы.

(1) «РЮКЗАК» (англ.: KNAPSACK).

Дано: a₁,...,a_n, b.

Спрашивается: Имеются ли индексы J 1,…, n  с  b 

(2) ГАМИЛЬТОНОВ ЦИКЛ.

Дано: ненаправленный граф G = (V, E).

Спрашивается: содержит ли G гамильтонов цикл (т.е. цикл, со­держащий все узлы)?

(3) ЗАДАЧА КОММИВОЯЖЕРА.

Дано: матрица M = (M_ij) размерности n  n «расстояний между n городами» и число k.

Спрашивается: имеется ли перестановка  («кругосветное пу­тешествие»), такая, что M_{i i}  M_{n}  k?

(4) ПРОБЛЕМА ПРИНАДЛЕЖНОСТИ СЛОВА ДЛЯ КОНТЕКСТНО-ЗАВИСИМОГО ЯЗЫКА.

Дано: контекстно-зависимая грамматика G = (, , P, S) и слово w^*.

Спрашивается: wL{G}?

Проблемы (1), (2), (3) лежат в NP и являются, таким образом, NP-пол­ными. Это до сих пор не показано относительно задачи (4). Задача (4), та­ким образом, может оказаться «ещё более трудной», чем NP-полные про­блемы.