informatique (MP2I/MPI) · Chapitre 31 · Application directe du cours
Problème — SAT : vérifier est facile, chercher ne l'est pas
Décidabilité et classes de complexité · niveau 3 (difficile)
Énoncé
- Écrire l'algorithme exhaustif pour sat, et donner sa complexité.
- Écrire le vérificateur, et donner la sienne.
- Mesurer les deux, et commenter l'écart.
- Que se passerait-il si l'on trouvait un algorithme polynomial pour sat ?
Corrigé de la question 1
1. L'exhaustif. Une formule en forme normale conjonctive sur variables et clauses. On énumère les valuations.
pour chaque entier k de 0 a 2^n - 1
val <-- les n bits de k
si toutes les clauses sont satisfaites par val
alors rendre val
rendre "insatisfiable"Terminaison : la boucle est bornée. Correction : on essaie toutes les valuations ; si aucune ne convient, il n'y en a pas. Complexité : dans le pire cas — atteint exactement quand la formule est insatisfiable, puisqu'il faut alors aller au bout.
Question 2 : comment l'IA t'aide
2. Écrire le vérificateur, et donner la sienne.
Élève
Je ne vois pas ce que reçoit le vérificateur. S'il ne reçoit que la formule, il doit chercher une valuation, et on retombe sur l'exhaustif.
IA
Tout est là : un vérificateur reçoit la formule et un certificat. Pour sat, quel objet convaincrait quelqu'un, d'un seul coup d'œil, que la formule est satisfiable ?
Élève
Une valuation qui la satisfait. Le vérificateur n'a alors plus rien à chercher, seulement à contrôler.
IA
Exactement. À quel moment peut-il conclure négativement en parcourant la formule, combien d'opérations fait-il en fonction de , et quelle est la taille du certificat ?
L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.
Continue cet exercice avec l'IA
Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.
Continuer avec l'IA — gratuit, sans inscriptionGratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.