Ich habe mehrere Orte gesehen, die einfach gesagt haben, dass es bekannt ist, dass P eine Teilmenge des Schnittpunkts von NP und Co-NP ist. Beweise, die zeigen, dass P eine Teilmenge von NP ist, sind nicht schwer zu finden. Um zu zeigen, dass es sich um eine Teilmenge der Schnittmenge handelt, muss lediglich gezeigt werden, dass P eine Teilmenge von Co-NP ist. Was könnte ein Beweis dafür sein? Vielen Dank!Warum ist P ⊆ Co-NP?
Die Klasse P unter Komplementierung geschlossen: wenn L eine Sprache in P, dann das Komplement von L ist auch in P ist. Sie können dies sehen, indem Sie einen beliebigen Polynomzeitentscheider für L verwenden und die Zustände annehmen und ablehnen umschalten; diese neue Maschine entscheidet nun das Komplement von L und tut dies in polynomieller Zeit.
Eine Sprache L ist in NP wenn sein Komplement ist in NP. Betrachten Sie also jede Sprache L ∈ P. Das Komplement von L ist auch in P, so das Komplement von L ist daher in NP (weil P & subseteq; NP). Daher ist L in NP. Folglich P & subsete; NP.
Hoffe, das hilft!
Denken Sie auf diese Weise. Betrachten Sie die Klasse co-P. Da P unter Komplement geschlossen ist, ist P = co-P.
Es sollte auch klar sein, dass Co-P eine Teilmenge von Co-NP ist, weil P in NP enthalten ist. Da P = co-P ist, folgt daraus, dass P in Co-NP enthalten ist.
Ich persönlich stört diese Frage hier nicht, aber wenn andere object, können Sie auch auf http://cs.stackexchange.com fragen –
Diese Frage scheint off-topic zu sein, weil es um Mathematik geht –