Complémentaire (complexité)

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

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

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.

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

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.

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

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

pour toute fonction ${\displaystyle s(n)\geq \log n}$.

En particulier NL=co-NL.

Il est conjecturé que ${\displaystyle 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.