Clique $ leq_p $ sat

Question

J'essaye de réduire la clique à SAT:

• Donné: graphique g = (sommets V, bords e) et $ k in mathbb {n} $
• Sortie: F formulaire tel que si G contient un sous-graphe complet de la taille K, le formulaire est satisfait (et vice versa).

J'ai essayé de le faire comme Cook / Levin a montré que SAT est NP-Complete en introduisant un ensemble de booléens $ v_i $ pour chaque sommet et $ e_ {i, j} $ pour un bord qui va de $ v_i $ à $ v_j $. Maintenant si $ v_i $ fait partie de la clique, alors $ e_ {i, j} $ Doit être vrai si $ v_j $ est également dans la clique.

Nous pouvons donc conclure que $ v_i land v_j implique e_ {i, j} $ Et c'est pour vrai pour au moins $ i, j in {0, ..., k - 1 } $ et $ i neq j $. Nous devons également nous assurer qu'aucun bord qui n'existe pas ne peut être défini sur vrai:$ bigwedge _ {(i, j) notin e} lnot , e_ {i, j} $.

Je ne sais pas si je suis de la bonne manière ou si je peux manquer quelque chose.

1. Comment pourrais-je restreindre le formulaire $ v_i land v_j implique e_ {i, j} $ être vrai pour au moins k variables?
2. Est-ce que cette façon est en poly-temps?
3. Y a-t-il une meilleure façon?