満足度を確認するためのアルゴリズム

Question

SATがNPにあることを証明するために、多項式の時間Verfier（アルゴリズム）を思いつく必要があります。Cooks Levin Theoremは、決定的なチューリングマシンを使用していますが、それは私が探しているものではありません。

アルゴリズムの考え方は、値を入れて答えを計算することです。その後、答えが1かどうかを確認します。ただし、私は「価値観を置く」部分のためにPsueDocodeを書くことができ、それからそれが確実に多項式であることを示す方法を理解することができません。

if x = 1:
 accept
else:
 reject

.

これはO（1）にある可能性があります。しかし、残りの部分はどうですか？

Answer 1

これは私がそれをする方法です：

ALGO：閉鎖の配列として与えられたDNF-SAT問題のための検証者およびブール値へのリテラルのマッピングの可能性 入力：
クロージャの配列：[ $ c_1 $ 、 $ c_2 $ 、...、 $ c_m $ ]
$ c_j \ subseteq \ {x_1、...、x_n、\ gr x_1、... \ x_n \} $ （証明書）配列 $ m $ ここで、 $ m_i $ はliteral $ 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 

.

注：数学表記はインデントされており、擬似コードで一般的に使用されているSTACKEXCHANGEはそれをサポートしていません