title: Complémentaire (complexité)
text: # 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
  
  ### Complémentaire d'un langage
  
  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
  
  Soit C une classe, alors son complémentaire co-C est : $co{\text{-}}C=\{U\subseteq \Sigma ^{*}|{\bar {U}}\subseteq C\}$.
  
  ### 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.
  
  ## Propriété de l'opérateur "complémentaire" (co-)
  
  ### Au niveau des langages
  
  * $co{\text{-}}(co{\text{-}}C)=C$
  * $C\subseteq C'\Rightarrow co{\text{-}}C\subseteq co{\text{-}}C'$
  
  ### 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.
  
  ## Théorèmes
  
  ### 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é :
  
      ${\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
  
  Il est conjecturé que $co{\text{-}}NP\neq NP$, mais cela n'a jamais été démontré. 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.
  
  