Partiel de modèles de calcul et complexité Natacha Portier le 24 mars 2000

Notes de cours et de TD autorisées Rédaction soignée indispensable !

Effet Shannon

Question 1,1

Combien y a-t-il de fonctions booléennes de n variables ? Combien y a-t-il de graphes orientés avec p sommets ? Donner un majorant du nombre de circuits booléens de taille p.

Définition

Un ensemble X de mots booléens est un problème P/poly s’il existe un polynôme p et une suite de circuits booléens (C_{n}(x_{1}, ..., x_{n}))_{n∈N} tels que pour tout entier n le circuit C_{n} ait une seule sortie et soit de taille au plus p(n), et tout n-uplet booléen a_{1}, ..., a_{n} appartienne à X si et seulement si C_{n}(a_{1}, ..., a_{n}) calcule 1.

Question 1,2

Montrer que pour tout polynôme p il existe un entier n et une fonction booléenne de n variables qui n’est calculée par aucun circuit de taille p(n).

Question 1,3

En déduire qu’il existe un problème qui n’est pas P/poly.

Question 2

Le problème DIV ERGE − SUR − P LACE est l’ensemble des machines de Turing M qui ont un calcul divergent qui utilise seulement les |M| premiers symboles du ruban (|M| est la taille de la description de la machine). Montrer que ce problème est ESPACE-P, puis qu’il est ESPACE-P-complet en utilisant une réduction du problème ACCEP T E − SUR − P LACE.

Problèmes périodiques

Définitions

Considérons une instance de SAT : un ensemble de n clauses {C_{1}, ..., C_{n}} qui utilisent les variables {x_{1}, ..., x_{m}} et {x_{1}^{+1}, ..., x_{m}^{+1}}. Nous lui associons un ensemble infini de variables {x_{1}^{i}, ..., x_{m}^{i}|i ∈ Z} et un ensemble infini de clauses {C_{1}^{i}, ..., C_{n}^{i}|i ∈ Z} telles que pour tout entier i et tout entier j compris entre 1 et n :

C_{j}^{i}(x_{1}^{i}, ..., x_{m}^{i}, x_{1}^{i+1}, ..., x_{m}^{i+1}) = C_{j}(x_{1}, ..., x_{m}, x_{1}^{+1}, ..., x_{m}^{+1})

Par exemple à

\{ \begin{matrix}x_{1} ∨ ¬x_{2}^{+1} \\ x_{1} ∨ x_{2} \end{matrix}

nous associons

\{ \begin{matrix}… \\ x_{1}^{i−1} ∨ ¬x_{2}^{i} \\ x_{1}^{i−1} ∨ x_{2}^{i−1} \\ x_{1}^{i} ∨ ¬x_{2}^{i+1} \\ x_{1}^{i} ∨ x_{2}^{i} \\ x_{1}^{i+1} ∨ ¬x_{2}^{i+2} \\ x_{1}^{i+1} ∨ x_{2}^{i+1} \\ … \end{matrix}

Cet ensemble infini de clauses est satisfiable s’il existe une valuation sur l’ensemble des variables ( i.e. une fonction de {x_{1}^{i}, ..., x_{m}^{i}|i ∈ Z} dans {0; 1}) qui satisfasse toutes les clauses. Cette valuation v est de période p si pour tous i et j elle vérifie v(x_{j}^{i}) = v(x_{j}^{i+p}).

Un ensemble de n clauses des variables {x_{1}, ..., x_{m}} et {x_{1}^{+1}, ..., x_{m}^{+1}} est dans SAT − P ERIODIQUE si l’ensemble infini de clauses associé est satisfiable.

Nous fixons pour la question suivante un ensemble de n clauses {C_{1}, ..., C_{n}} qui utilisent les ensembles de variables {x_{1}, ..., x_{m}} et {x_{1}^{+1}, ..., x_{m}^{+1}} et nous considérons les ensembles périodiques associés {x_{1}^{i}, ..., x_{m}^{i}|i ∈ Z} et {C_{1}^{i}, ..., C_{n}^{i}|i ∈ Z}.

Question 3,1

Montrer que si {C_{1}^{i}, ..., C_{n}^{i}|i ∈ Z} est satisfiable alors il l’est par une valuation de période au plus exponentielle en m.

Question 3,2

Montrer que SAT − P ERIODIQUE est ESPACE-P.

Question 3,3

Montrer que SAT − P ERIODIQUE est ESPACE-P-complet en utilisant DIV ERGE−SUR−P LACE. On pourra s’inspirer de la preuve du théorème de Cook.

Définitions

Définissons maintenant un graphe périodique. Soit G un graphe fini non orienté dont les sommets sont {x_{1}, ..., x_{m}} et {x_{1}^{+1}, ..., x_{m}^{+1}}. Le graphe périodique associé est un graphe dont les sommets sont {x_{1}^{i}, ..., x_{m}^{i}|i ∈ Z} et dont les arcs sont {(x_{j}^{i}, x_{k}^{i})|i ∈ Z et (x_{j}, x_{k})est une arête de G} ∪ {(x_{j}^{i}, x_{k}^{i+1})|i ∈ Z et (x_{j}, x_{k}^{+1})est une arête de G}.

Un tel graphe infini est k-coloriable s’il existe une fonction de l’ensemble de ses sommets dans {1; ...; k} (ensemble des couleurs) telle que deux sommets adjacents n’aient pas la même couleur. Cette coloration f est de période p si pour tous i et j elle vérifie f(x_{j}^{i}) = f(x_{j}^{i+p}).

Un graphe de sommets {x_{1}, ..., x_{m}} et {x_{1}^{+1}, ..., x_{m}^{+1}} avec un entier k est dans GRAP HE − P ERIODIQUE − COLORIABLE si le graphe infini périodique associé est k-coloriable.

Question 4,1

Montrer que GRAP HE −P ERIODIQUE −COLORIABLE est ESPACE-P.

Question 4,2

Montrer que GRAP HE −P ERIODIQUE −COLORIABLE est ESPACE-P-complet. On pourra s’inspirer du cas non-périodique (cf annexe ci-dessous) en définissant et démontrant soigneusement les analogues pour le cas périodique.

Annexe

Lemme 1 : NAE − SAT est NP-dur.

Un ensemble de clauses avec trois littéraux (variable ou négation de variable) par clause est dans NAE − SAT s’il existe une valuation telle que chaque clause a au moins un littéral vrai et au moins un littéral faux.

Idée de la preuve : Par réduction de 3 − SAT. Á chaque clause c = a_{1} ∨ a_{2} ∨ a_{3} nous associons deux clauses c′ = a_{1} ∨ a_{2} ∨ x et c′′ = ¬x ∨ a_{3} ∨ F où x est une variable fraîche.

Lemme 2 : GRAP HE − COLORIABLE est NP-dur.

Un couple (graphe G, entier k) est dans GRAP HE − COLORIABLE s’il existe un coloriage avec k couleurs de ses sommets tel que deux sommets adjacents n’aient jamais la même couleur. Pour montrer ce lemme nous réduisons NAE − SAT à GRAP HE − COLORIABLE.

Idée de la preuve :