Exhaustivité NP du problème 3-SAT [Fermé

Question

J'ai commencé à lire sur la complexité algorithmique pour mon travail de thèse. Ont déjà étudié sur la réductibilité du temps polynomial, NP-Complete, NP-dur. Essayant maintenant de prouver l'exhaustivité NP de certains des problèmes classiques. J'ai commencé avec un problème de 3 pour sa crédibilité.

Problème de 3-SAT - s'est avéré être NP-Complete:

Entrée: une formule boléenne F dans CNF où chaque clause contient au plus trois variables.

Question: Cette formule est-elle satisfaisante?

Montrez maintenant que le problème simple en 3-SAT est également NP-Complete:

Entrée: une formule boléenne F dans CNF où chaque clause contient au plus trois variables et seules les clauses de longueur deux peuvent contenir des variables niées.

Question: Cette formule est-elle satisfaisante?

Peut-on expliquer l'idée principale? Merci en avance.