алгоритм проверки удовлетворения

Question

Для того, чтобы доказать, что SAT находится в NP, мне нужно подняться многочленным временем Verfier (алгоритм).Теорема повара Левин использует недетерминированную машину Turing, но это не то, что я ищу.

Идея алгоритма может быть то, что мы вкладываем значения и рассчитаем ответ.Затем мы проверяем, является ли ответ 1 или нет.Тем не менее, я не могу понять, как я могу написать PSuedoCode для «помещения в части ценностей», а затем показать, что это многочлен наверняка.

if x = 1:
 accept
else:
 reject

.

Это может быть в O (1).Но как насчет оставшейся части?

Answer 1

Вот как я это сделал:

Algo: verifier для проблем с DNF-SAT, приведенные как массив замкнувшими и возможным отображением литералов на логические <Сильный> вход:

Массив закрытий: [ $ C_1 $ , $ C_2 $ , ..., $ c_m $ ]





где $ C_J \ SOUNTEDQ \ {x_1, ..., x_n, \ neg x_1, ... \ neg x_n \} $
(Сертификат) Массив $ m $ где $ m_i $ - это логическое значение литерала $ x_i $
Выход: true или false

for $i = 1$ to $m$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $\neg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true 

.

Примечание. Математическая запись отступается и обычно используется в псевдокоде, к сожалению, CS Stockexchange не поддерживает его