Algoritmo per il controllo della soddisfazione

Question

Per dimostrare che Sat è in NP, ho bisogno di trovare un tempo di tempo polinomiale (un algoritmo).I cuochi Levin Teorem utilizza una macchina di Turing non deterministica ma non è quello che sto cercando.

L'idea dell'algoritmo potrebbe essere che abbiamo inserito i valori e calcola la risposta.Quindi, controlliamo se la risposta è 1 o meno.Tuttavia, non riesco a capire come potrei scrivere un Psuelocode per la parte "mettendo in valori" e poi mostrare che è sicuramente polinomiale.

if x = 1:
 accept
else:
 reject

.

Questo potrebbe essere in O (1).Ma per quanto riguarda la parte rimanente?

Answer 1

Ecco come lo farei:

Algo: Verificatore per il problema DNF-SAT dato come array di chiusure e una possibile mappatura di letterali ai booleani

Input:
Array di chiusure: [ $ c_1 $ , $ c_2 $ , ..., $ c_m $ ]
dove $ c_j \ subeteq \ {x_1, ..., x_n, \ neg x_1, ... \ neg x_n \} $
(Certificato) array $ m $ dove $ m_i $ è il valore booleano della classe letterali $ x_i $
Uscita: True o 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 

.

Nota: la notazione matematica è rientrata e comunemente usata in pseudocode tristemente cs stackexchange non supportarlo