Complémentaire (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Complémentaire.

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. Cette opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP.

Définition formelle[modifier | modifier le code]

Complémentaire d'un langage[modifier | modifier le code]

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 | modifier le code]

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

En termes de machines de Turing[modifier | modifier le code]

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 | modifier le code]

Au niveau des langages[modifier | modifier le code]

  •  co-(co-C)=C
  • C \subseteq C' \Rightarrow co-C \subseteq co-C'

Au niveau des machines[modifier | modifier le code]

Dans le cas des classes déterministes, les classes et leurs 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 | modifier le code]

Le théorème d'Immerman-Szelepcsényi[modifier | modifier le code]

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[modifier | modifier le code]

Il est conjecturé que co-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 | modifier le code]

Notes et références[modifier | modifier le code]

  1. Sylvain Perifel, Complexité algorithmique, Ellipses,‎ 2014 (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 »)