Corrigé Centrale 2026 Informatique MPI — Partie C, V (Q35 à Q39) : NP-complétude de TOTAL-DSAT

Sujet officiel du concours Centrale, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Mêmes notations que Q16 à Q34. dsat est le problème de la satisfiabilité d'une formule déontique.
Q35. dsat est NP-complet si et seulement si dsat est dans NP.

On conjecture que dsat n'est pas dans NP. Un univers est total si tout monde est idéal pour tout monde, y compris pour lui-même : $R_{U} (i, j)$ pour tous $i$ , $j$ . Une formule est satisfiable dans un univers total $U$ s'il existe un monde $i$ de $U$ avec $U ⊨_{i} φ$ .
Q36. Il existe une formule satisfiable qui n'est satisfiable dans aucun univers total.
Q37. Pour $φ$ réduite et $U$ total à $N$ mondes, on peut tester $U ⊨_{i} φ$ en $O (N ∣ φ ∣)$ , où $∣ φ ∣$ est la taille de l'arbre de $φ$ .

$T$ est un témoignage de $φ$ dans $U$ si $T$ est un sous-graphe total de $U$ et si, pour toute sous-formule $◊ ψ$ de $φ$ , dès qu'un monde $k$ de $U$ vérifie $U ⊨_{k} ψ$ , l'un de ces mondes est dans $T$ .
Q38. Pour $φ$ réduite et $U$ total, si $U ⊨_{i} φ$ , il existe un témoignage $T$ de $φ$ contenant $i$ , de taille polynomiale en celle de $φ$ , avec $T ⊨_{i} φ$ .
Q39. total-dsat (étant donnée $φ$ déontique, existe-t-il un univers total $B$ et un monde $i$ avec $B ⊨_{i} φ$ ?) est NP-complet.

Corrigé

On utilise les définitions du cours : un problème de décision est dans NP si toute instance positive admet un certificat de taille polynomiale vérifiable en temps polynomial ; il est NP-difficile si tout problème de NP s'y réduit polynomialement, NP-complet s'il est de plus dans NP ; sat est NP-complet (théorème de Cook-Levin, admis). Le lemme suivant sert deux fois.

Lemme. Soit $φ$ une formule propositionnelle (sans $□$ ni $◊$ ). Pour tout univers $U$ et tout monde $i$ , $U ⊨_{i} φ$ si et seulement si la valuation de $i$ satisfait $φ$ au sens propositionnel : par induction sur $φ$ , les clauses de $⊨_{i}$ pour les variables, $\land$ , $\lor$ , $\to$ , $\neg$ ne regardent que le monde $i$ et coïncident avec les tables de vérité. Par conséquent, $φ$ est satisfiable (propositionnellement) si et seulement si elle a un modèle déontique, et ce modèle peut être pris total : si $v$ satisfait $φ$ , l'univers à un seul monde $v$ muni d'une boucle est total et le satisfait ; réciproquement, la valuation d'un monde $i$ tel que $U ⊨_{i} φ$ satisfait $φ$ .

Q35. Le sens direct est la définition : un problème NP-complet est dans NP. Réciproquement, supposons dsat dans NP ; il reste à voir qu'il est NP-difficile, par une réduction $s a t ⩽_{p} d s a t$ . À une formule propositionnelle $φ$ , instance de sat, on associe la même formule, vue comme formule déontique : la traduction est une simple recopie, en temps linéaire. D'après le lemme, $φ$ est une instance positive de sat si et seulement si c'en est une de dsat. Comme sat est NP-complet, tout problème de NP se réduit à sat, donc à dsat par composition de réductions polynomiales : dsat est NP-difficile, et NP-complet dès qu'il est dans NP. Ce que le correcteur attend : le sens de la réduction (du problème connu, sat, vers dsat), et la justification que la réduction préserve les réponses dans les deux sens.

Q36. La formule de l'exemple du sujet, $\neg Q \land □ Q$ , convient. Elle est satisfiable : l'univers $E$ la satisfait au monde $i$ ( $Q$ est faux en $i$ et vrai en ses deux successeurs $j$ et $k$ ). Mais dans un univers total $U$ , tout monde $i$ est son propre successeur : $U ⊨_{i} □ Q$ impose $U ⊨_{i} Q$ , ce qui contredit $U ⊨_{i} \neg Q$ . Aucun monde d'un univers total ne la satisfait. (Autrement dit, dans un univers total, $□ φ \to φ$ est toujours vraie ; c'est faux en général.)

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →