Algorithmes et Complexite desProblemes de Satisfaction de Contraintes
(cours no 3)
Nicolas (Miki) Hermann
LIX, Ecole Polytechnique
1/41 Miki Hermann Algorithmes et complexite des csp (3)
Nouvelles fonctions a partir d’anciennes
Si nous avons deux fonctions booleennes
bor0(x, y) = (x ∨ y) et not(x) = ¬x
nous pouvons construire une nouvelle fonction
bor1(x, y) = (x ∨ ¬y)
par la composition bor0(x, not(y)).Ainsi, nous pouvons construire la fonction majorite a partir de laconjonction and(x, y) = (x ∧ y) et de la disjonctionor0(x, y, z) = (x ∨ y ∨ z) :
maj(x, y, z) = or0(and(x, y), and(y, z), and(z, x))
= (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)
2/41 Miki Hermann Algorithmes et complexite des csp (3)
Exercice 8
1 Construisez la fonction
aff(x, y, z) = x + y + z (mod 2)
a partir des fonctions and(x, y) = (x ∧ y) et not(x) = ¬x.
2 Construisez la fonction and(x, y) a partir des fonctionsbor0(x, y) = (x ∨ y) et not(x).
3 Construisez la fonction bor0(x, y) a partir de aff(x, y, z) etand(x, y).
3/41 Miki Hermann Algorithmes et complexite des csp (3)
Regles de construction des fonctions
Definition
Soit B un ensemble de fonctions pas forcement de meme arite.L’ensemble [B] contient toutes les fonctions construites a partir de cellesde B. L’ensemble [B] est construit par saturation :
Introduction : Si f(~x) ∈ B alors f(~x) ∈ [B].
Permutation : Si f(x1, . . . , xk) ∈ [B] et π est une permutation de{1, . . . , k}, alors nous avons f(xπ(1), . . . , xπ(k)) ∈ [B].
Diagonalisation : Si f(x1, . . . , xk−1, xk) ∈ [B] etf ′(x1, . . . , xk−1) = f(x1, . . . , xk−1, xk−1), alorsf ′(x1, . . . , xk−1) ∈ [B].
Composition : Si f(~x, y) ∈ [B] et g(~z) ∈ [B], alors f(~x, g(~z)) ∈ [B].
Cylindrification : Si f(~x) ∈ [B] alors f ′(~x, y) = f(~x) ∈ [B].
4/41 Miki Hermann Algorithmes et complexite des csp (3)
Regles alternatives
La derniere regle peut etre remplacee par une autre, plus simple, de sorteque nous avons :
Introduction : Si f(~x) ∈ B alors f(~x) ∈ [B].
Permutation : Si f(x1, . . . , xk) ∈ [B] et π est une permutation de{1, . . . , k}, alors nous avons f(xπ(1), . . . , xπ(k)) ∈ [B].
Diagonalisation : Si f(x1, . . . , xk−1, xk) ∈ [B] etf ′(x1, . . . , xk−1) = f(x1, . . . , xk−1, xk−1), alorsf ′(x1, . . . , xk−1) ∈ [B].
Composition : Si f(~x, y) ∈ [B] et g(~z) ∈ [B], alors f(~x, g(~z)) ∈ [B].
Projection : La fonction prm
k(x1, . . . , xm, . . . , xk) = xm appartient
a [B] pour chaque k et m = 1, . . . , k.
5/41 Miki Hermann Algorithmes et complexite des csp (3)
Clones et leur topologie
Definition
Si f ∈ [B], on dit que l’ensemble de fonctions B construit la fonction f .
Definition
Un ensemble de fonctions F contenant toutes les projections et ferme parcompositions s’appelle un clone.
Theorem
Soit B un ensemble de fonctions. L’ensemble sature de fonctions [B] est
un clone.
Attention
Ne pas confondre 〈B〉 et [B].
6/41 Miki Hermann Algorithmes et complexite des csp (3)
Clones et leur proprietes
Proprietes de clones
Les ensembles de fonctions B et leurs clones [B] satisfont les quatreproprietes suivantes :
1 B ⊆ [B]
2 B ⊆ B′ implique que [B] ⊆ [B′]
3 [[B]] = [B]
Remarque
Les memes identites sont satisfaites aussi par les ensembles de relations Set leurs co-clones 〈S〉, i.e.,
1 S ⊆ 〈S〉
2 S ⊆ S′ implique que 〈S〉 ⊆ 〈S′〉
3 〈〈S〉〉 = 〈S〉
7/41 Miki Hermann Algorithmes et complexite des csp (3)
Comment classifier les clones ?
Remarque
Pour chaque ensemble de fonctions B il existe un clone [B], mais deuxensembles B et B′ de fonctions differentes peuvent engendrer le memeclone [B] = [B′]. Pour pouvoir classifier les clones, nous avons d’abordbesoin de quelques structures algebriques supplementaires.
Definition
Une relation binaire ≤ ⊆ A × A sur un ensemble A s’appelle un ordrepartiel si elle satisfait les conditions suivantes pour chaque tripletd’elements a, b, c ∈ A :
Reflexivite : a ≤ a
Antisymetrie : a ≤ b et b ≤ a implique a = b
Transitivite : a ≤ b et b ≤ c implique a ≤ c
8/41 Miki Hermann Algorithmes et complexite des csp (3)
Treillis
Definition
Un ordre partiel ≤ sur un ensemble A s’appelle un ordre de treillis s’ilsatisfait les deux conditions supplementaires :
4 Pour chaque a, b ∈ A il existe un c ∈ A, tel que c ≤ a et c ≤ b, etpour chaque d ∈ A les relations d ≤ a et d ≤ b impliquent d ≤ c.L’unique element c s’appelle l’infimum de a et b, note par a ⊓ b.
5 Pour chaque a, b ∈ A il existe un c ∈ A, tel que a ≤ c et b ≤ c, etpour chaque d ∈ A les relations a ≤ d et b ≤ d impliquent c ≤ d.L’unique element c s’appelle le supremum de a et b, note par a ⊔ b.
6 La structure (A, ⊔, ⊓) s’appelle un treillis.
9/41 Miki Hermann Algorithmes et complexite des csp (3)
Treillis de Post
Soit B l’ensemble des clones. La structure B est partiellement ordonneepar l’inclusion ⊆ de clones (inclusion ensembliste). Les operationsd’infimum et supremum sont respectivement l’intersection ∩ et l’union ∪ensembliste. Donc la structure (B,∪,∩) forme un treillis. Dans le casbooleen on l’appelle familierement le
Treillis de Post
Question
Quelle est la structure du treillis de Post ?
Reponse
Elle a ete etablie par Emil Post (1857 – 1954) entre 1920 et 1940. Lapreuve de 120 pages a ete publiee en 1941.
10/41 Miki Hermann Algorithmes et complexite des csp (3)
I2
I1 I0
I
N2
N
L2
L3L1 L0
L
V2
V1 V0
V
E2
E1 E0
E
D2
D1
D
M2
M1 M0
M
R2
R1 R0
BF
S00
S01S02
S0
S3
00
S3
01S3
02
S3
0
S2
00
S2
01S2
02
S2
0
S10
S11 S12
S1
S3
10
S3
11S3
12
S3
1
S2
10
S2
11S2
12
S2
1
11/41 Miki Hermann Algorithmes et complexite des csp (3)
Bases des clones
Il est indesirable de travailler avec toutes les fonctions du clone [B].Existe-t-il pour chaque clone un sous-ensemble fini de fonctions a partirdesquelles nous pouvons engendrer le clone par saturation ? On prefere lesous-ensemble le plus petit.
Definition
Soit B un clone. Chaque ensemble B0 ⊆ B, tel que [B0] = B, s’appelleun generateur de B. Si B0 est un generateur de B et pour chaqueensemble B1 ( B0 nous avons [B1] 6= B, alors B0 s’appelle une basede B. Autrement dit, une base est un generateur minimal par inclusion.
Theorem (Post)
Chaque clone booleen possede une base fini.
Remarque
La preuve tient sur 8 pages. Un clone peut avoir plusieurs bases.
12/41 Miki Hermann Algorithmes et complexite des csp (3)
Fonctions pour les bases
Les fonctions booleennes suivantes jouent un role dans l’etablissement debases des clones.
Constantes : 0 et 1.
Unaires : id(x) = x et not(x) = ¬x.
Binaires : and(x, y) = (x ∧ y) et or(x, y) = (x ∨ y).
Ternaires : maj(x, y, z) = (x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x) etaff(x, y, z) = x + y + z (mod 2).
13/41 Miki Hermann Algorithmes et complexite des csp (3)
Clones interessants
I2
I1 I0
N2
L2V2 E2
D2
Classification des clones interessants
1 clone trivial : I2.
7 clones minimaux non-triviaux : I0, I1, N2, E2, V2, L2, D2.
14/41 Miki Hermann Algorithmes et complexite des csp (3)
Bases des clones interessants
Clone Nom BaseI2 identite {id}I0 constante 0 {id, 0}I1 constante 1 {id, 1}N2 negation {not}E2 conjonction {and}V2 disjonction {or}L2 affinite {aff}D2 majorite {maj}
15/41 Miki Hermann Algorithmes et complexite des csp (3)
Reformulation des resultats connus
Pol(R) ⊇ I2 ⇐⇒ R est une relation booleenne
Pol(R) ⊇ I0 ⇐⇒ R est 0-valide
Pol(R) ⊇ I1 ⇐⇒ R est 1-valide
Pol(R) ⊇ N2 ⇐⇒ R est complementive
Pol(R) ⊇ E2 ⇐⇒ R est Horn
Pol(R) ⊇ V2 ⇐⇒ R est dual Horn
Pol(R) ⊇ L2 ⇐⇒ R est affine
Pol(R) ⊇ D2 ⇐⇒ R est bijonctive
16/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance entre clones et co-clones
Correspondance entre les inclusions
L’observation du Treillis de Post nous indique l’existence des deuxproprietes suivantes :
Si S1 ⊆ S2 alors Pol(S1) ⊇ Pol(S2) pour chaque paired’ensembles de relation booleennes S1, S2.
Si B1 ⊆ B2 alors Inv(B1) ⊇ Inv(B2) pour chaque paired’ensembles de fonctions booleennes B1, B2.
Correspondance de Galois
Une telle correspondance a ete etudiee la premiere fois par Evariste Galois(1811 – 1832).
17/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance de Galois
Definition
Soit A = (A,�A) et B = (B,�B) deux structures avec leurs ordrespartiels. Deux fonctions α : A → B et β : B → A forment unecorrespondance de Galois entre A et B si les quatre proprietes suivantessont satisfaites :
1 a �A b implique α(b) �B α(a) pour chaque a, b ∈ A.
2 c �B d implique β(d) �A β(c) pour chaque c, d ∈ B.
3 a �A β(α(a)) pour chaque a ∈ A.
4 b �B α(β(b)) pour chaque b ∈ B.
Question
Existe-t-il une correspondance de Galois entre les clones B et lesco-clones A ?
18/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance de Galois
Question
Prenons pour α la fonction Pol et pour β la fonction Inv. Les deuxpremieres conditions de la Definition de correspondance de Galois sontdeja etablies. Quid des deux autres ?
Reponse
OUI, car les inclusions S ⊆ Inv(Pol(S)) et B ⊆ Pol(Inv(B)) sonttoujours satisfaites.
Theorem
Soit A l’ensemble de tous les co-clones et B l’ensemble de tous les clones
sur un domaine fini. Les fonctions Pol: A → B et Inv : B → A forment
une correspondance de Galois.
Exercice 10
Prouvez formellement le Theoreme precedent.
19/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance de Galois
Il existe encore un resultat plus fort et plus interessant.
Theorem
Soit S un ensemble de relations et F un ensemble de fonctions sur un
domaine fini. Alors les egalites suivantes sont satisfaites :
Inv(Pol(S)) = 〈S〉
Pol(Inv(F )) = [F ]
20/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance de Galois sur les treillis
Theorem
Soit (A,⊔A,⊓A), (B,⊔B,⊓B) deux treillis et α : A → B, β : B → Adeux fonction formant une correspondance de Galois sur ce treillis. Alors
les identite suivantes sont valides pour chaque a1, a2 ∈ A et b1, b2 ∈ B :
1 α(a1 ⊔A a2) = α(a1) ⊓
B α(a2)
2 α(a1 ⊓A a2) = α(a1) ⊔
B α(a2)
3 β(b1 ⊔B b2) = β(b1) ⊓
A β(b2)
4 β(b1 ⊓B b2) = β(b1) ⊔
A β(b2)
Demonstration.
Exercice !
21/41 Miki Hermann Algorithmes et complexite des csp (3)
Modularite de Pol et Inv
Question
Comment determiner le clone ou le co-clone si nous avons l’ensemble derelations ou l’ensemble de fonctions presente par parties ?
Corollary
Soit S1, S2 deux ensembles de relations et F1, F2 deux ensembles de
fonctions. Alors les identites suivantes sont valides :
1 Pol(S1 ∪ S2) = Pol(S1) ∩ Pol(S2)
2 Inv(F1 ∪ F2) = Inv(F1) ∩ Inv(F2)
Demonstration.
Les clones (B,∪,∩) ainsi que les co-clones (A,∪,∩) forment des treillis.Les fonctions Pol et Inv determinent une correspondance de Galois entreles clones et les co-clones.
22/41 Miki Hermann Algorithmes et complexite des csp (3)
Correspondance de Galois et complexite des csp
Remarque
Il n’est pas necessaire de considerer le co-clone entier 〈S〉, il suffittoujours de travailler avec l’ensemble de relations S d’origine.
Theorem
Soit S un ensemble de relations. Les problemes de satisfaction de
contraintes csp(S) et csp(〈S〉) sont polynomialement equivalents.
Demonstration.
Etant donne l’inclusion S ⊆ 〈S〉, la reduction polynomiale de csp(S) acsp(〈S〉) est triviale.L’ensemble de relations S implante le co-clone 〈S〉. Par consequent, nouspouvons ecrire chaque formule ϕ du csp(〈S〉) comme une formuleequivalente ϕ′ du csp(S). L’implantation ϕ′ est polynomiale par rapporta la formule d’origine ϕ. Ceci determine la reduction polynomiale decsp(〈S〉) a csp(S).
23/41 Miki Hermann Algorithmes et complexite des csp (3)
Reducibilite entre les csp
Question
Si nous avons deux ensembles de relations S1 et S2, comment determinerla relation entre csp(S1) et csp(S2), surtout si S1 et S2 sontincomparables ?
Theorem
Soit S1 et S2 deux ensembles de relations. Si Pol(S1) ⊇ Pol(S2) alors il
existe une reduction polynomiale de csp(S1) a csp(S2).
Demonstration.
Si Pol(S1) ⊇ Pol(S2) alors Inv(Pol(S1)) ⊆ Inv(Pol(S2)). Parconsequent, 〈S1〉 ⊆ 〈S2〉, ce qui nous donne la reduction polynomiale decsp(〈S1〉) a csp(〈S2〉). Le Theoreme precedent implique qu’il existe alorsune reduction polynomiale de csp(S1) a csp(S2).
24/41 Miki Hermann Algorithmes et complexite des csp (3)
csp NP-complets
Il nous faut d’abord determiner quel sont les problemes de satisfaction decontraintes generique NP-complets. Nous avons deja vu que
csp(or0, or3) = csp(or0, or1, or2, or3) = 3sat
est NP-complet, mais ils comportent trop de relations. Il nous faudrait uncsp NP-complet engendre par une seule relation.Un bon candidat pour engendrer les csp NP-complets est la relation
1-in-3 = {001, 010, 100}.
25/41 Miki Hermann Algorithmes et complexite des csp (3)
1-in-3
Theorem
csp(1-in-3) est NP-complet.
Demonstration.
Il nous faut construire a partir de la relation 1-in-3 un ensemble derelations S tel que csp(S) est NP-complet. Nous savons deja quecsp(neq, or0) = 3sat, donc il nous suffira d’implanter les relations
neq = {01, 10}
or0 = {001, 010, 011, 100, 101, 110, 111}
par la relation 1-in-3. . . . / . . .
26/41 Miki Hermann Algorithmes et complexite des csp (3)
1-in-3
Demonstration (cont).
1 Nous allons d’abord produire les constantes 0 et 1 par identificationde variables. Notons que
[1-in-3(xT , xF , xF )] = {100}
donc par la contrainte 1-in-3(xT , xF , xF ) nous forcon la variable xT
de representer 1 et la variable xF de representer 0.
2 Notons aussi que
[1-in-3(x, y, 0)] = {01, 10}
ce qui nous donne la possibilite de produire la relation neq. Ainsi,nous avons l’implantation de la contrainte
neq(x, y) = ∃xT∃xF 1-in-3(x, y, xF ) ∧ 1-in-3(xT , xF , xF )
. . . / . . .
27/41 Miki Hermann Algorithmes et complexite des csp (3)
Demonstration.
3 Pour implanter or0 c’est un peu plus complique, mais on y arrive.
or0(x1, x2, x3) = ∃y2∃y3∃z1∃z2∃z3∃z4∃z5
1-in-3(x1, z1, z2) ∧ 1-in-3(y2, z1, z3)
∧ 1-in-3(y3, z2, z4) ∧ 1-in-3(z2, z3, z5)
∧ neq(x2, y2) ∧ neq(x3, y3)
4 Il est facile maintenant d’implanter les relations or1, or2 et or3 paror0 et neq. Ceci prouve que la relation 1-in-3 implante les relationsnecessaires pour le probleme 3sat.
28/41 Miki Hermann Algorithmes et complexite des csp (3)
nae
Pour prouver que la relation nae engendre des csp NP-complets, il nousfaut d’abord quelques lemmes.
Lemma
La formule ϕ(x1, . . . , xk) est satisfaisable si et seulement si la disjonction
ϕ(x1, . . . , xk) ∨ ϕ(¬x1, . . . ,¬xk) est satisfaisable.
Demonstration.
Si ϕ(x1, . . . , xk) est satisfaisable alors ϕ(x1, . . . , xk) ∨ ϕ(¬x1, . . . ,¬xk)est satisfaisable aussi.Si ϕ(x1, . . . , xk) ∨ ϕ(¬x1, . . . ,¬xk) alors il existe un modele m quisatisfait la disjonction. Soit m |= ϕ(x1, . . . , xk), et dans ce cas la preuveest terminee, soit m |= ϕ(¬x1, . . . ,¬xk) et dans ce cas¬m |= ϕ(x1, . . . , xk).
29/41 Miki Hermann Algorithmes et complexite des csp (3)
1-in-3 and nae
Les relations 1-in-3 et nae contiennent les vecteurs suivants :
1-in-3 ={
001, 010, 100}
nae =
{
001, 010, 100110, 101, 011
}
Par consequent, nous avons l’identite
1-in-3(x, y, z) ∨ 1-in-3(¬x,¬y,¬z) = nae(x, y, z)
Notons aussi que la relation nae implante neq par diagonalisation.
[neq(x, y)] = [nae(x, y, y)] = {01, 10}.
Pour chaque vecteur booleen m ∈ {0, 1}k, la fonction w(m) calculeson poids de Hamming.
30/41 Miki Hermann Algorithmes et complexite des csp (3)
Complexite de csp(nae)
Theorem
csp(nae) est NP-complet.
Demonstration.
Soit ϕ une 1-in-3-formule, i.e., formule construite a partir de larelation 1-in-3. Construisons la nae-formule ϕ′ par remplacement.Pour chaque clause 1-in-3(x, y, z) dans ϕ nous ajoutons la clausenae(x, y, z) dans ϕ′. Si m |= ϕ alors m |= ϕ′ car 1-in-3 ⊆ nae.
Soit ϕ′ une nae-formule et m une valuation telle que m |= ϕ′. Pourchaque clause c = nae(x1, x2, x3) de ϕ′ soit mc la restriction de maux variables {x1, x2, x3} qui satisfait c. Nous construisons unenouvelle nae-formule ϕ′′ par remplacement. Si w(mc) = 1 nousajoutons la clause c dans ϕ′′. Si w(mc) = 2, nous remplacons laclause c, ou m(x) = 1, par la formule∃y nae(y, x2, x3) ∧ neq(x1, y). Notons qu’on peut implanter narelation neq aussi bien par nae que par 1-in-3.
. . . / . . .
31/41 Miki Hermann Algorithmes et complexite des csp (3)
Demonstration.
A partir de la nae-formule ϕ′′, nous construisons la 1-in-3-formule ϕpar remplacement. Nous remplacons dans ϕ′′ chaque clausenae(x, y, z) par 1-in-3(x, y, z) et chaque clauseneq(x, y) = nae(x, y, y) par
neq(x, y) = ∃xT∃xF 1-in-3(x, y, xF ) ∧ 1-in-3(xT , xF , xF )
Ainsi, pour chaque vecteur m, si m |= ϕ′ alors m |= ϕ.
32/41 Miki Hermann Algorithmes et complexite des csp (3)
Dichotomie des csp booleens
Nous sommes finalement en pouvoir de prouver le resultat tant annoncedepuis le debut.
Theorem (Theoreme Dichotomique (Schaefer, 1978))
Soit S un ensemble de relations booleennes. Si S satisfait l’une des
conditions suivantes
1 S est 0-valide,
2 S est 1-valide,
3 S est Horn,
4 S est dual Horn,
5 S est bijonctive,
6 S est affine,
alors csp(S) est decidable en temps polynomial. Sinon, csp(S) est
NP-complet.
33/41 Miki Hermann Algorithmes et complexite des csp (3)
Demonstration.
Nous faisons une analyse par cas selon les 8 clones interessants I2, I0, I1,N2, E2, V2, L2 et D2, les cas polynomiaux d’abord.
1 Si Pol(S) ⊇ I0, i.e., S est 0-valide, alors chaque relation dans Scontient le vecteur 0 · · · 0. Donc chaque instance de csp(S) estsatisfaisable par la valuation 0 · · · 0.
2 Si Pol(S) ⊇ I1, i.e., S est 1-valide, alors chaque relation dans Scontient le vecteur 1 · · · 1. Donc chaque instance de csp(S) estsatisfaisable par la valuation 1 · · · 1.
3 Si Pol(S) ⊇ E2, i.e., S est ferme par rapport a la conjonction,alors S est Horn. HornSat est polynomial, donc chaque instancede csp(S) est decidable en temps polynomial.
4 Si Pol(S) ⊇ V2, i.e., S est ferme par rapport a la disjonction,alors S est dual Horn. Donc csp(S) est decidable en tempspolynomial par dualite avec le cas Horn.
. . . / . . .
34/41 Miki Hermann Algorithmes et complexite des csp (3)
Demonstration.
5 Si Pol(S) ⊇ L2, i.e., S est ferme par rapport a l’affinite, alors Sest affine. AffineSat est polynomial, donc, csp(S) est decidableen temps polynomial.
6 Si Pol(S) ⊇ D2, i.e., S est ferme par rapport a la majorite, alors Sest bijonctif. 2Sat est polynomial, donc csp(S) est decidable entemps polynomial.
7 Si Pol(S) = N2, i.e., S est ferme par rapport a la negation,alors S est complementif. Etant donne que nae est complementive,nous avons nae ∈ 〈S〉. Par consequent, csp(S) est NP-complet.
8 Si Pol(S) = I2, i.e., S n’est ferme que par rapport a l’identite,alors S est un ensemble de relations booleennes. Etant donne que1-in-3 ∈ Inv(I2), nous avons 1-in-3 ∈ 〈S〉. Par consequent, csp(S)est NP-complet.
35/41 Miki Hermann Algorithmes et complexite des csp (3)
Quelques remarques
Une fois le treillis de Post ainsi que la correspondance de Galois entreles clones et co-clones connus, la preuve du Theoreme Dichotomique(Theoreme sur la dichotomie des csp booleens) est un jeu d’enfants.
La preuve d’origine par Schaefer est totalement differente et plusdifficile a comprendre.
36/41 Miki Hermann Algorithmes et complexite des csp (3)
Preuves faciles
Nous pouvons maintenant aborder des problemes de satisfaction avec unefacilite inoui.
Probleme Monotone 3neg-2pos Sat
Entree: Un ensemble de variables V et une formule ϕ en CNF sur V , ouchaque clause est constituee soit de trois litteraux negatifs, soit de deuxlitteraux positifs.
Question: La formule ϕ est-elle satisfaisable ?
37/41 Miki Hermann Algorithmes et complexite des csp (3)
Preuves faciles
Theorem
Monotone 3neg-2pos Sat est NP-complet.
Demonstration.
Le probleme correspond au csp([¬x ∨ ¬y ∨ ¬z], [x ∨ y]). La relation[¬x ∨ ¬y ∨ ¬z] est Horn, la relation [x ∨ y] est dual Horn et bijonctive. Ilest donc facile a voir que Pol([¬x ∨ ¬y ∨ ¬z], [x ∨ y]) = I2. Parconsequent, le probleme Monotone 3neg-2pos Sat estNP-complet.
38/41 Miki Hermann Algorithmes et complexite des csp (3)
Solution d’un Exercice
Nous pouvons repondre facilement aux questions posees auparavent :
1 csp(or0, or1) est polynomial, car Pol(or0, or1) ⊇ V2
(exactement Pol(or0, or1) = V1).
2 csp(or0, or3) appele aussi Monotone 3Sat est NP-complet, carPol(or0, or3) = I2.
3 csp(or2, or3) est polynomial, car Pol(or2, or3) ⊇ E2
(exactement Pol(or2, or3) = E0).
4 csp(or1, or2) est NP-complet, car Pol(or1, or2) = I2.
Rappel des relations
or0 = [x ∨ y ∨ z]
or1 = [x ∨ y ∨ ¬z]
or2 = [x ∨ ¬y ∨ ¬z]
or3 = [¬x ∨ ¬y ∨ ¬z]
39/41 Miki Hermann Algorithmes et complexite des csp (3)
Exercice
Determinez si les csp(S) sont polynomiaux ou NP-complets pour lesensembles de relations booleennes S suivants :
1 S = {[(x ∧ ¬y) ≡ z]}
2 S = {[(x 6≡ y) ≡ z], [(x ∨ y) ≡ z]}
3 S = {[(x 6≡ y) ≡ z], [(x ∧ y) ≡ z]}
4 S = {[(x ≡ y) ≡ z], [(x ∨ y) ∧ z]}
40/41 Miki Hermann Algorithmes et complexite des csp (3)