Un problème SAT peut-il être un problème NP complet ?
La question de savoir si un problème de satisfiabilité booléenne (SAT) peut être un problème NP-complet est une question fondamentale en théorie de la complexité computationnelle. Pour répondre à cette question, il est essentiel de considérer les définitions et les propriétés de la complétude NP et d'examiner le contexte historique et théorique qui sous-tend la classification du SAT comme un problème NP-complet.
Définitions et contexte
Problème SAT: Le problème SAT consiste à déterminer s'il existe une affectation de valeurs de vérité aux variables qui rend une formule booléenne donnée vraie. Une formule booléenne est généralement exprimée sous forme normale conjonctive (CNF), où la formule est une conjonction de clauses et chaque clause est une disjonction de littéraux. Par exemple, une formule pourrait ressembler à :
![\[ (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "Rendu par QuickLaTeX.com")
NP (temps polynomial non déterministe): Un problème de décision est en NP si une solution donnée peut être vérifiée comme correcte ou incorrecte en temps polynomial par une machine de Turing déterministe. Essentiellement, si vous disposez d’une solution candidate, vous pouvez vérifier efficacement sa validité.
NP-Complet: Un problème est NP-complet s’il satisfait à deux conditions :
1. C'est en NP.
2. Chaque problème de NP peut s’y réduire en temps polynomial.
Le concept de NP-complétude a été introduit par Stephen Cook dans son article fondateur de 1971 « The Complexity of Theorem-Proving Procedures », dans lequel il a démontré que le problème SAT est le premier problème NP-complet connu. Ce résultat est maintenant connu sous le nom de théorème de Cook.
Théorème de Cook et ses implications
Pour comprendre pourquoi SAT est NP-complet, nous devons établir deux points clés :
1. SAT est en NP.
2. Tout problème en NP peut être réduit à SAT en temps polynomial.
SAT est en NP
Pour vérifier que SAT est dans NP, considérons qu'étant donné une formule booléenne et une proposition d'attribution de valeurs de vérité à ses variables, nous pouvons vérifier si la formule est évaluée comme vraie en temps polynomial. Cela implique d'évaluer chaque clause de la formule pour voir si au moins un littéral dans chaque clause est vrai. Étant donné que l’évaluation d’une formule booléenne est un processus simple qui implique un nombre fini d’opérations logiques, cela peut être effectué efficacement. Ainsi, SAT est en NP car on peut vérifier une solution en temps polynomial.
Réduction du temps polynomial
La partie la plus difficile de prouver que SAT est NP-complet est de montrer que chaque problème dans NP peut être réduit à SAT en temps polynomial. Cela implique de démontrer que pour tout problème en NP, il existe une fonction calculable en temps polynomial qui transforme les instances du problème en instances de SAT de telle sorte que le problème d'origine ait une solution si et seulement si l'instance SAT transformée est satisfiable.
Pour illustrer cela, considérons un problème générique 
en NP. Par définition, il existe une machine de Turing à temps polynomial non déterministe 
qui décide . La machine dispose d'un processus de vérification en temps polynomial qui peut vérifier si un certificat (solution) donné est valide. Nous pouvons coder le fonctionnement de sur une entrée 
comme une formule booléenne telle que la formule est satisfiable si et seulement si accepte .
L'encodage implique les étapes suivantes :
1. Codage de configuration: Encodez les configurations (états, contenus de la bande et positions des têtes) de comme variables booléennes. Chaque configuration peut être représentée par une séquence de bits.
2. Encodage des transitions: Encode la fonction de transition de comme un ensemble de contraintes booléennes. Ces contraintes garantissent que les transitions valides entre les configurations sont capturées.
3. États initiaux et acceptants: Encodez la configuration initiale (lorsque la machine démarre) et la configuration d'acceptation (lorsque la machine s'arrête et accepte) sous forme de contraintes booléennes.
En construisant une formule booléenne qui capture le comportement de , nous créons une instance de SAT qui est satisfiable si et seulement s'il existe une séquence de transitions valides menant à un état acceptant. Cette réduction peut être effectuée en temps polynomial par rapport à la taille de l'entrée .
Exemple : réduction de 3-SAT à SAT
Pour élucider davantage le concept de réduction du temps polynomial, considérons le cas spécifique de la réduction de 3-SAT en SAT. Le problème 3-SAT est un cas particulier de SAT où chaque clause comporte exactement trois littéraux. Pour réduire 3-SAT à SAT, nous pouvons simplement observer que toute instance de 3-SAT est déjà sous la forme requise par SAT (c'est-à-dire une formule CNF). Par conséquent, la réduction est triviale et peut être effectuée en temps linéaire, ce qui est une réduction en temps polynomial.
Implications du fait que SAT soit NP-complet
La classification de SAT comme NP-complète a de profondes implications pour la théorie de la complexité informatique et la résolution pratique de problèmes. Puisque SAT est NP-complet, tout problème dans NP peut être traduit en une instance SAT. Cette universalité signifie que SAT sert de référence pour la complexité d'autres problèmes. Si nous pouvons trouver un algorithme en temps polynomial pour résoudre SAT, nous pouvons résoudre tous les problèmes NP en temps polynomial, ce qui implique 
.
À l’inverse, si nous prouvons qu’il n’existe aucun algorithme en temps polynomial pour SAT, cela impliquerait que 
. Malgré des recherches approfondies, la question de savoir si reste l’un des problèmes ouverts les plus importants en informatique.
Applications pratiques
En pratique, les solveurs SAT sont largement utilisés dans divers domaines, notamment la vérification de logiciels, l'intelligence artificielle et la cryptographie. Les solveurs SAT modernes exploitent des algorithmes et des heuristiques sophistiqués pour gérer efficacement des instances volumineuses et complexes, malgré le caractère NP-exhaustif théorique de SAT. Ces solutions ont permis de résoudre des problèmes du monde réel qui étaient auparavant insolubles.
Conclusion
Le problème SAT est en effet un problème NP-complet, comme l'établit le théorème de Cook. Cette classification est basée sur le fait que SAT est en NP et que tout problème en NP peut être réduit à SAT en temps polynomial. Les implications du fait que SAT soit NP-complet sont considérables, influençant à la fois la recherche théorique et les applications pratiques en informatique.
D'autres questions et réponses récentes concernant Complexité:
- La classe PSPACE n'est-elle pas égale à la classe EXPSPACE ?
- La classe de complexité P est-elle un sous-ensemble de la classe PSPACE ?
- Pouvons-nous prouver que les classes Np et P sont identiques en trouvant une solution polynomiale efficace pour tout problème NP complet sur une MT déterministe ?
- La classe NP peut-elle être égale à la classe EXPTIME ?
- Existe-t-il des problèmes dans PSPACE pour lesquels il n’existe aucun algorithme NP connu ?
- Un problème peut-il appartenir à la classe de complexité NP s'il existe une machine de Turing non déterministe qui le résoudra en temps polynomial
- NP est la classe de langages dotés de vérificateurs de temps polynomial
- P et NP sont-ils réellement la même classe de complexité ?
- Tous les langages sans contexte appartiennent-ils à la classe de complexité P ?
- Y a-t-il une contradiction entre la définition de NP comme une classe de problèmes de décision avec des vérificateurs en temps polynomial et le fait que les problèmes de la classe P ont également des vérificateurs en temps polynomial ?
Voir plus de questions et réponses dans Complexité