Cricca $ leq_p $ sab

Question

Sto cercando di ridurre la cricca in sabato:

• Dato: grafico G = (Vertices V, Edges E) e $ k in mathbb {n} $
• Output: Formular F tale che se G contiene un sottografo completo della dimensione K, il formulare è soddisfacente (e viceversa).

Ho provato a farlo nel modo in cui Cook/Levin ha dimostrato che SAT è NP-completo introducendo una serie di booleani $ v_i $ per ogni vertice e $ e_ {i, j} $ per un vantaggio che va da $ v_i $ a $ v_j $. Ora se $ v_i $ fa parte della cricca, quindi $ e_ {i, j} $ Deve essere vero iff $ v_j $ è anche nella cricca.

Quindi possiamo concludere, quello $ v_i land v_j implica e_ {i, j} $ E questo è vero per almeno per $ i, j in {0, ..., k - 1 } $ e $ i neq j $. Inoltre, dobbiamo assicurarci che nessun vantaggio che non esiste possa essere impostato su True:$ bigwedge _ {(i, j) notin e} lnot , e_ {i, j} $.

Non so se sono nel modo corretto o se potrei perdere qualcosa.

1. Come limiterei il formulare $ v_i land v_j implica e_ {i, j} $ essere vero per almeno K variabili?
2. È così in poli-time?
3. C'è un modo migliore?