Complémentaire (complexité)
De Wikipedia, l'encyclopédie encyclopedia
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. Cet opérateur amène à considérer de nouvelles classes comme co-NP, le complémentaire de NP.
Complémentaire d'un langage
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
Soit C une classe, alors son complémentaire co-C est[1] : .
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.
Au niveau des langages
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.
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é :
pour toute fonction .
En particulier NL=co-NL.
Problèmes ouverts
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.
- (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 »)
- 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 »)