Complémentaire (complexité)

Modèle:Homon En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe. Cet opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP.

Définition formelle

Complémentaire d'un langage

Soit $L$ un langage sur l'alphabet $\mathrm{\Sigma }$, et ${\mathrm{\Sigma }}^{*}$, l'ensemble des mots sur $\mathrm{\Sigma }$. Alors le complémentaire de $L$, noté ici $\overline{L}$ est ${\mathrm{\Sigma }}^{*}\setminus L$. On remarque en particulier que le complémentaire de $\overline{L}$ est $L$.

Complémentaire d'une classe de langages

Soit C une classe, alors son complémentaire co-C est : $co\text{-}C=\{U\subseteq {\mathrm{\Sigma }}^{*}|\overline{U}\in C\}$.

En termes de machines de Turing

Si on prend le point de vue des machines de Turing et des problèmes, le problème de décision complémentaire est celui où l'on a inversé "oui" et "non" pour répondre à la question.

Propriété de l'opérateur "complémentaire" (co-)

Au niveau des langages

• $co\text{-}(co\text{-}C)=C$
• $C\subseteq C^{\prime }\Rightarrow co\text{-}C\subseteq co\text{-}{C}^{\prime }$

Au niveau des machines

Dans le cas des classes déterministes, les classes et leur complémentaire sont égales : il suffit d'inverser les réponses données, ce qui n'est pas le cas pour une machine non-déterministe puisque l'existence d'un chemin acceptant n'est pas équivalent au fait que tous les chemins soient acceptants.

Théorèmes

Le théorème d'Immerman-Szelepcsényi

Dans sa forme générale, le théorème d'Immerman-Szelepcsényi énoncé l'égalité :

$\text{NSPACE}(s(n))=\text{co-NSPACE}(s(n))$

pour toute fonction $s(n)\ge \log n$.

En particulier NL=co-NL.

Problèmes ouverts

Il est conjecturé que $co\text{-}NP\ne NP$, mais cela n'a jamais été démontré. Cette question est liée au problème P=NP de la façon suivante : si P=NP alors NP=co-NP car P=co-P.

Bibliographie

• Modèle:Computational Complexity (Arora et Barak)