Ψ Die Informatikseite

Menü

coNP

Sei $C$ eine Komplexitätsklasse

\begin{displaymath}coC\end{displaymath}

besteht aus allen Sprachen $L$, deren Komplement $\overline{L}$ in $C$ liegt.

Für alle deterministischen Komplexitätsklassen gilt

\begin{displaymath}coC=C\end{displaymath}

also z.B.

\begin{displaymath}coP=P\end{displaymath}


\begin{displaymath}coPSPACE=PSPACE\end{displaymath}

, da sich die Ausgabe einfach vertauschen läßt.
Dies läßt sich für nichtdeterministische Sprachen nicht durchführen, da das ,,Raten'' der Belegung nicht mitspielt. Wir können zum Beispiel das komplementäre Problem von $SAT$ $\overline{SAT}$ konstruieren, daß immer dann ,,JA'' zurückgibt, wenn die eigegebene Formel nicht erfüllbar ist und ,,NEIN'' zurückgibt, wenn sie erfüllbar ist. Schmeißen wir nun unser ,,Orakel'' an, so gibt es uns eine Belegung, wo die Formel nicht erfüllbar ist, falls es eine gibt. Wir wissen dann jedoch nicht, ob die Formel für alle Belegungen unerfüllbar ist. Wir können also mit der einfachen Umkehr des Verfahrens kein korrektes Verfahren bekommen.