Comment prouvez-vous que SAT est NP-complet?

Question

Comme il est, comment peut-on prouver que SAT est NP-complet?

Je sais ce que cela signifie par NP-complet, donc je ne ai pas besoin d'explication à ce sujet.

Ce que je veux savoir est comment savez-vous que l'un problème, comme SAT est NP-complet sans recourir à la réduction à d'autres problèmes tels que le problème hamiltonien ou autre.

Answer 1

Je crois que 3-SAT a été réduite de la satisfiabilité plus générale dans le document de Karp qui décrit 21 problèmes NP-complets .

Wikipedia a une description de la façon de montrer que SATISFAISABILITÉ est NP-complet, résultat qui est connu comme Cook-Levin théorème . L'idée de cette preuve est de montrer que toute machine de Turing non déterministes polynomiale peut être modélisé comme une expression booléenne avec la taille polynomiale. L'expression booléenne a des termes pour représenter l'espace de configuration valide de la machine de Turing: où la tête de bande est, ce que l'état actuel est, quels symboles sont écrits sur la bande, et quelles transitions sont valables à chaque position. Parce que le MFO arrêtera en temps polynomial, l'espace de configuration est limitée et nous pouvons faire une (grande) expression polynomiale pour le représenter.