CML C

Question 1

Dans quels cas un CSP peut-il être résolu en temps polynomial ?

Answer 1

• Si son langage est facile
• Si sa structure est facile

Question 2

Qu’est-ce qu’un langage de contraintes ?

Answer 2

Un ensemble fini de fonctions booléennes sur un domaine D fini

Question 3

Qu’est-ce que CSP(Γ) avec Γ un langage de contraintes ?

Answer 3

L’ensemble des CSPs restreint aux réseaux dans lesquels chaque contrainte utilise une fonction de Γ

Question 4

Qu’est-ce qu’un gadget ?

Answer 4

Une construction utilisée pour prouver qu’une famille de réseaux CSP(Γ) est NP-dure

Question 5

Qu’est-ce qu’un formule primitive-positive (pp-formule) sur un langage Γ ?

Answer 5

Une formule qui utilise uniquement la conjonction, le quantificateur existentiel, l’égalité et les fonctions de Γ

Question 6

Qu’est-ce qu’un fonction primitive-positive définissable (pp-définissable) sur un langage Γ ?

Answer 6

Une fonction c pour laquelle il existe une pp-formule φ sur Γ telle que (d₁, …, d_r) ∈ c ⇔ φ(d₁, …, d_r) est vrai

Question 7

Théorème du folklore

Answer 7

Si toute c ∈ Γ₁ est pp-définissable sur Γ₂, alors il existe une réduction en temps polynomial de CSP(Γ₁) vers CSP(Γ₂)

Question 8

Qu’est-ce que le clone relationnel d’un langage Γ ?

Answer 8

C’est l’ensemble ⟨Γ⟩ des fonctions pp-définissables sur Γ

Question 9

Quels sont les liens entre la complexité de CSP(Γ) et les fonctions de ⟨Γ⟩ ?

Answer 9

• 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

Question 10

Qu’est-ce qu’un polymorphisme ?

Answer 10

Soit Γ un langage de contraintes sur D, f : D^k → D est un polymorphisme k-aire de Γ si ∀ c ∈ Γ, ∀ τ₁, …, τ_k ∈ c, f(τ₁, …, τ_k) ∈ c

Question 11

Qu’est-ce que Pol(Γ) ?

Answer 11

L’ensemble des polymorphismes du langage Γ

Question 12

Quelles sont les propriétés de l’ensemble Pol(Γ) ?

Answer 12

• Il contient toutes les projections
• Il est clos par composition

Question 13

Théorème de Geiger

Answer 13

Soient Γ₁ et Γ₂ deux langages sur un même domaine D, Γ₂ ⊆ ⟨Γ₁⟩ ⇔ Pol(Γ₁) ⊆ Pol(Γ₂)

Question 14

Quels polymorphismes garantissent à un langage Γ de pouvour être résolu en temps polynomial s’ils sont dans Pol(Γ) ?

Answer 14

• Les polymorphismes de Semilattice
• La majorité
• La minorité
• Le polymorphisme de Mal’tsev

Question 15

Quels sont les polymorphismes de Semilattice ?

Answer 15

• f(a, a) = a
• f(a, b) = f(b, a)
• f(f(a, b), c) = f(a, f(b, c))

Question 16

Quels est le polymorphisme de Mal’tsev ?

Answer 16

f(a, a, b) = f(b, a, a) = b

Question 17

Théorème de Schaefer

Answer 17

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)

Question 18

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a) = 0 ?

Answer 18

Il suffit de renvoyer vrai

Question 19

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a) = 1 ?

Answer 19

Il suffit de renvoyer vrai

Question 20

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b) = a ∨ b ?

Answer 20

Il suffit d’appliquer l’arc-cohérence

Question 21

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b) = a ∧ b ?

Answer 21

Il suffit d’appliquer l’arc-cohérence

Question 22

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b, c) = majorité(a, b, c) ?

Answer 22

Il suffit d’appliquer la singleton arc-cohérence

Question 23

Comment résoudre polynomialement un réseau de CSP(Γ) si Γcontient le polymorphisme f(a, b, c) = minorité(a, b, c) ?

Answer 23

Il suffit d’appliquer l’élimination gaussienne

Question 24

Théorème de la dichotomie (Bulatov et Zhuk)

Answer 24

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)

Question 25

Théorème de Dalmau et Pearson

Answer 25

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 {a₁, …, a_k} = {b₁, …, b_k} alors f(a₁, …, a_k) = f(b₁, …, b_k)

Question 26

Qu’est-ce qu’un langage à largeur bornée ?

Answer 26

Un langage Γ tel qu’il existe k fini pour lequel la k-cohérence permet de résoudre CSP(Γ)

Question 27

Qu’est-ce qu’une weak near-unanimity operation (WNU) ?

Answer 27

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)

Question 28

Théorème de Barto et Kozik

Answer 28

Γ 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)

Question 29

Comment résoure un réseau CSP(Γ) tel que Γ a une largeur bornée ?

Answer 29

En appliquant la singleton arc-cohérence

Question 30

Qu’est-ce qu’une contraite connected row-convex ?

Answer 30

Une contrainte dont les couples acceptés forment une aire connectée dans la matrice de compatibilité de la contrainte