Co-NP definert ved formelle språk

Co-NP defineres som alle språk (problemer), $L$, s.a $\bar{L}\in NP$, der $\bar{L}$ er komplementet til $L$ (altså alle strenger som ikke er i $L$).