algoritmo para verificar satisfiability

Question

Para provar que o SAT é NP, eu precisa vir para cima com um tempo polinomial verfier (um algoritmo).Os Cozinheiros Levin Teorema usa uma máquina de Turing não determinística, mas que não é o que eu estou procurando.

A idéia do algoritmo é que vamos colocar nos valores e calcular a resposta.Em seguida, vamos verificar se a resposta for 1 ou não.No entanto, eu sou incapaz de entender como eu poderia escrever um psuedocode para a "colocação em valores de "parte" e, em seguida, mostrar que é polinomial, com certeza.

if x = 1:
 accept
else:
 reject

Isso poderia ser em O(1).Mas o que sobre a parte restante?

Answer 1

Aqui está como eu faria isso:

Detalhe: O verificador de DESISTÊNCIA-SÁB problema dado como matriz de encerramentos e de um possível mapeamento de literais booleanos
Entrada:
Matriz de encerramento:[$C_1$,$C_2$,...,$C_m$]
onde $C_j \subseteq \{x_1,...,x_n, eg x_1, ... eg x_n\}$
(Certidão) De Matriz $M$ onde $M_i$ é o valor booleano da literal $x_i$
Saída: verdadeiro ou falso

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

Nota:a notação matemática é recuado e comumente utilizado em pseudocódigo, infelizmente, cs stackexchange não suporta isso