Classification of Scheduling Problems

Доказательство

• «Выполнимость»  NP.

Доказательство сводимости

• Пусть Π=(X,Y) будет любая другая проблема в NP.
• Требуется доказать, что Π полиномиально сводится к «Выполнимости».
• По определению существует полином p и задача распознавания Π'=(X',Y') из P, такие что
• X' = {x#c: x  X, c  {0,1}└ p(size(x))┘} и
• Y = {y  X :  c  {0,1}└ p(size(x))┘ : y#c  Y'}.
• Пусть Φ:{0,…,N}× A{⊔}→{-1,…,N}×A{⊔}×{-1,0,1} – полиномиальная машина Тьюринга для Π' с алфавитом A.
• Пусть полином q : time(Φ,x#c) ≤ q(size(x#c)) для всех примеров x#c  X'.
• size(x#c) = size(x) + 1 + └p(size(x))┘

Основная идея

• Сконструировать набор Z(x) дизъюнкций над множеством V(x) булевых переменных для каждого x  X, так что Z(x) выполнимо тогда и только тогда, когда x  Y.

Булевы переменные

• Q:=q(size(x) + 1 + └p(size(x))┘)
• V(x):
• vijσ , 0 ≤ i ≤ Q, -Q ≤ j ≤ Q и σA{⊔}= (после i шагов вычислений в j-й позиции строки записан символ σ);
• wijn , 0 ≤ i ≤ Q, -Q ≤ j ≤ Q и −1≤ n ≤ N; (после i шагов вычислений j-я позиция строки просматривается и оператор n выполняется).

Итоговая цель

• Если (n(i),s(i),π(i)) i = 0,1,2,…тройка из вычисления Φ, то требуется определить набор дизъюнкций таким образом, что
• vijσ = true  sj(i) =σ;
• wijn = true  π(i) = j и n(i) = n;
• набор Z(x) дизъюнкций выполним  существует строка c, такая что output(Φ,x#c)=1.

Требуемые условия для выполнимого набора дизъюнкций

• На каждом шаге вычислений каждая позиция содержит единственный символ.
• На каждом шаге вычислений ровно одна позиция просматривается, и один оператор выполняется.
• Вычисление начинается со входа x#c для некоторого c {0,1}└ p(size(x))┘.
• Алгоритм работает корректно. ((n,σ)=(m,τ,δ))
• Алгоритм останавливается, если n(i)=−1.
• Не просмотренные позиции не изменяются.
• Алгоритм на выходе получает 1.

На каждом шаге вычислений каждая позиция содержит единственный символ.

На каждом шаге вычислений ровно одна позиция просматривается, и один оператор выполняется.

Вычисление начинается со входа x#c для некоторого c{0,1}└ p(size(x))┘.

Алгоритм работает корректно. ((n,σ)=(m,τ,δ)).

Алгоритм останавливается, если n(i) = −1.

Не просмотренные позиции не изменяются.

Алгоритм на выходе получает 1.

• {vQ,1,1}, {vQ,2,⊔}

Полиномиальность сведения

• Длина записи Z(x) O(Q3log Q)
• Число литералов O(Q3)
• запись индекса O(log Q)
• Так как Q ― это полином от size(x), то существует полиномиальный алгоритм, который по данному x, вычисляет Z(x).
• Осталось доказать, что Z(x) выполнима тогда и только тогда, когда x  Y.

• Z(x) выполнима. 
•  набор значений истинности T, на котором выполнены все дизъюнкции.
• Пусть c {0,1}└ p(size(x))┘, и cj = 1 для всех j c T(v0,size(x)+1+j,1) = true, и cj = 0 для всех j c T(v0,size(x)+1+j,1) = false.
• По построению переменные отражают вычисление  на входе x#c. 
• output(, x#c)=1.
•  ―алгоритм проверки сертификата. 
• x ― «да»-пример (x  Y).

• x  Y и c ― любой сертификат для x.
• Пусть (n(i),s(i),π(i)) i = 0, 1, …, m вычисление Φвходаx#c.
• T(vi,j,σ ) = true  sj(i) = σ
• T(wi,j,n ) = true  π(i) = j и n(i) = n.
• T(vi,j,σ ) = T(vi-1,j,σ ) i = m + 1,…, Q.
• T(wi,j,n ) = T(wi-1,j,n ) i = m + 1,…, Q. 
• T ― набор значений истинности, на котором выполнены все дизъюнкции из Z(x).

Задача «3-Выполнимость»

• Условие. Задано множество переменных U и набор Z дизъюнкций, каждая из которых содержит ровно 3 литерала.
• Вопрос. Является ли Z выполнимым?

3-Выполнимость

• Теорема 2.2 (Cook 1971)
• Задача «3-Выполнимость» является NP-полной.