Die Komplemente von Problemen in NP liegen nicht unbedingt in NP. Daher definieren wir die Klasse coNP, die per Definition genau die Komplemente von Problemen aus NP enthält.
Ja. Wenn irgendein Problem L gleichzeitig NP-vollständig und in coNP ist, dann lässt sich jedes Problem aus NP reduzieren auf L, also auf ein Problem in coNP. Da coNP abgeschlossen ist unter Polynomialzeitreduktionen, ist dann NP eine Teilmenge von coNP. Dann bleibt noch zu zeigen, dass coNP eine Teilmenge von NP ist. Dafür sei L' ein beliebiges Problem aus coNP. Wir können L' reduzieren auf das Komplement von SAT, da das coNP-vollständig ist. Die gleiche Reduktion ist auch eine Reduktion vom Komplement von L' auf SAT. Wir wissen schon, dass NP Teilmenge von coNP ist, also ist dann SAT in coNP, also ist das Komplement von SAT in NP. Die Reduktion von L' auf das Komplement von SAT zeigt nun, dass L' in NP ist. Also ist coNP eine Teilmenge von NP, und insgesamt folgt NP = coNP.
Ein Kompliment für dies gelungenes Video :P
Angenommen, man könnte zeigen das Primfaktorenzerlegung NP vollständig ist. Folgt daraus dann, dass NP = coNP?
Ja. Wenn irgendein Problem L gleichzeitig NP-vollständig und in coNP ist, dann lässt sich jedes Problem aus NP reduzieren auf L, also auf ein Problem in coNP. Da coNP abgeschlossen ist unter Polynomialzeitreduktionen, ist dann NP eine Teilmenge von coNP. Dann bleibt noch zu zeigen, dass coNP eine Teilmenge von NP ist. Dafür sei L' ein beliebiges Problem aus coNP. Wir können L' reduzieren auf das Komplement von SAT, da das coNP-vollständig ist. Die gleiche Reduktion ist auch eine Reduktion vom Komplement von L' auf SAT. Wir wissen schon, dass NP Teilmenge von coNP ist, also ist dann SAT in coNP, also ist das Komplement von SAT in NP. Die Reduktion von L' auf das Komplement von SAT zeigt nun, dass L' in NP ist. Also ist coNP eine Teilmenge von NP, und insgesamt folgt NP = coNP.