CML C Flashcards
Dans quels cas un CSP peut-il être résolu en temps polynomial ?
- Si son langage est facile
- Si sa structure est facile
Qu’est-ce qu’un langage de contraintes ?
Un ensemble fini de fonctions booléennes sur un domaine D fini
Qu’est-ce que CSP(Γ) avec Γ un langage de contraintes ?
L’ensemble des CSPs restreint aux réseaux dans lesquels chaque contrainte utilise une fonction de Γ
Qu’est-ce qu’un gadget ?
Une construction utilisée pour prouver qu’une famille de réseaux CSP(Γ) est NP-dure
Qu’est-ce qu’un formule primitive-positive (pp-formule) sur un langage Γ ?
Une formule qui utilise uniquement la conjonction, le quantificateur existentiel, l’égalité et les fonctions de Γ
Qu’est-ce qu’un fonction primitive-positive définissable (pp-définissable) sur un langage Γ ?
Une fonction c pour laquelle il existe une pp-formule φ sur Γ telle que (d1, …, dr) ∈ c ⇔ φ(d1, …, dr) est vrai
Théorème du folklore
Si toute c ∈ Γ1 est pp-définissable sur Γ2, alors il existe une réduction en temps polynomial de CSP(Γ1) vers CSP(Γ2)
Qu’est-ce que le clone relationnel d’un langage Γ ?
C’est l’ensemble ⟨Γ⟩ des fonctions pp-définissables sur Γ
Quels sont les liens entre la complexité de CSP(Γ) et les fonctions de ⟨Γ⟩ ?
- Un algorithme qui résout CSP(Γ) résout aussi CSP(Γ’) pour Γ’ ⊆ ⟨Γ⟩
- Si ⟨Γ⟩ contient un langage NP-dur, Γ est NP-dur
- Si ⟨Γ⟩ ne contient pas de langage NP-dur, Γ contient des polymorphismes non-triviaux
Qu’est-ce qu’un polymorphisme ?
Soit Γ un langage de contraintes sur D, f : Dk → D est un polymorphisme k-aire de Γ si ∀ c ∈ Γ, ∀ τ1, …, τk ∈ c, f(τ1, …, τk) ∈ c
Qu’est-ce que Pol(Γ) ?
L’ensemble des polymorphismes du langage Γ
Quelles sont les propriétés de l’ensemble Pol(Γ) ?
- Il contient toutes les projections
- Il est clos par composition
Théorème de Geiger
Soient Γ1 et Γ2 deux langages sur un même domaine D, Γ2 ⊆ ⟨Γ1⟩ ⇔ Pol(Γ1) ⊆ Pol(Γ2)
Quels polymorphismes garantissent à un langage Γ de pouvour être résolu en temps polynomial s’ils sont dans Pol(Γ) ?
- Les polymorphismes de Semilattice
- La majorité
- La minorité
- Le polymorphisme de Mal’tsev
Quels sont les polymorphismes de Semilattice ?
- f(a, a) = a
- f(a, b) = f(b, a)
- f(f(a, b), c) = f(a, f(b, c))
Quels est le polymorphisme de Mal’tsev ?
f(a, a, b) = f(b, a, a) = b
Théorème de Schaefer
Le langage de contraintes Γ peut être résolu en temps polynomial si et seulement si il a un des polymorphismes suivants :
- f(a) = 0
- f(a) = 1
- f(a, b) = a ∨ b
- f(a, b) = a ∧b
- f(a, b, c) = majority(a, b, c)
- f(a, b, c) = minority(a, b, c)
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a) = 0 ?
Il suffit de renvoyer vrai
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a) = 1 ?
Il suffit de renvoyer vrai
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b) = a ∨ b ?
Il suffit d’appliquer l’arc-cohérence
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b) = a ∧ b ?
Il suffit d’appliquer l’arc-cohérence
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b, c) = majorité(a, b, c) ?
Il suffit d’appliquer la singleton arc-cohérence
Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b, c) = minorité(a, b, c) ?
Il suffit d’appliquer l’élimination gaussienne
Théorème de la dichotomie (Bulatov et Zhuk)
Le langage de contraintes Γ peut être résolu en temps polynomial si et seulement si il a un polymorphisme tel que ∀ a, e, r ∈ D, f(a, r, e, a) = f(r, a, r, e)
Théorème de Dalmau et Pearson
Le langage de contraintes Γ peut être résolu par l’algorithme de l’arc-cohérence si et seulement si pour tout k > 0, il existe un polymorphisme f dans Γ qui est totalement symétrique, c’est à dire que si {a1, …, ak} = {b1, …, bk} alors f(a1, …, ak) = f(b1, …, bk)
Qu’est-ce qu’un langage à largeur bornée ?
Un langage Γ tel qu’il existe k fini pour lequel la k-cohérence permet de résoudre CSP(Γ)
Qu’est-ce qu’une weak near-unanimity operation (WNU) ?
Une opération f telle que ∀ a, b ∈ D, f(b, a, a, …, a, a) = f(a, b, a, …, a, a) = … = f(a, a, a, …, a, b)
Théorème de Barto et Kozik
Γ a une largeur bornée si et seulement si Γ a deux polymorphismes f et g d’arité 3 et 4 tels que ∀ a, b ∈ D, f(b, a, a) = g(b, a, a, a)
Comment résoure un réseau CSP(Γ) tel que Γ a une largeur bornée ?
En appliquant la singleton arc-cohérence
Qu’est-ce qu’une contraite connected row-convex ?
Une contrainte dont les couples acceptés forment une aire connectée dans la matrice de compatibilité de la contrainte
