Complémentaire (complexité)

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 modifier

Complémentaire d'un langage modifier

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

Complémentaire d'une classe de langages modifier

Soit C une classe, alors son complémentaire co-C est^[1] : $co{\text{-}}C=\{U\subseteq \Sigma ^{*}|{\bar {U}}\subseteq C\}$ .

En termes de machines de Turing modifier

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

Au niveau des langages modifier

$co{\text{-}}(co{\text{-}}C)=C$
$C\subseteq C'\Rightarrow co{\text{-}}C\subseteq co{\text{-}}C'$

Au niveau des machines modifier

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 modifier

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

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)\geq \log n$ .

En particulier NL=co-NL.

Problèmes ouverts modifier

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

Bibliographie modifier

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 2.6 (« coNP, EXP and NEXP »)

Notes et références modifier

↑ Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non-déterministe ») p.61.
↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 2.6.1 (« coNP »)

Portail de l'informatique théorique

[1] Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non-déterministe ») p.61.

[2] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 2.6.1 (« coNP »)

[1]

[2]