检查可靠性的算法

Question

为了证明SAT在NP中，我需要提出多项式时间Verfier（算法）。烹饪莱文定理使用非确定性图灵机，但这不是我正在寻找的。

算法的想法可能是我们输入的值并计算答案。然后，我们检查答案是否为1。但是，我无法理解我如何为“放入价值”部分来编写psuedocode，然后显示它是多项式的。

if x = 1:
 accept
else:
 reject

.

这可能是在O（1）中。但剩下的部分呢？

Answer 1

这里是我怎么做的：

algo：验证者用于DNF-SAT问题，作为封闭阵列和电学版的可能映射到Booleans

输入：
闭包数组：[ $ c_1 $ ， $ c_2 $ ，...， $ C_M $ ]
其中 $ c_j \ subseteq \ {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 Stackexchange不支持它