Complémentaire (complexité) — Wikipédia
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 | modifier le code]Complémentaire d'un langage
[modifier | modifier le code]Soit un langage sur l'alphabet , et , l'ensemble des mots sur . Alors le complémentaire de , noté ici est . On remarque en particulier que le complémentaire de est .
Complémentaire d'une classe de langages
[modifier | modifier le code]Soit C une classe, alors son complémentaire co-C est[1] : .
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]Au niveau des machines
[modifier | modifier le code]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 | 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é :
pour toute fonction .
En particulier NL=co-NL.
Problèmes ouverts
[modifier | modifier le code]Il est conjecturé que , 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]- (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 2.6 (« coNP, EXP and NEXP »)
Notes et références
[modifier | modifier le code]- Sylvain Perifel, Complexité algorithmique, Ellipses, , 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, (ISBN 0-521-42426-7), chap. 2.6.1 (« coNP »)