Widziałem kilka miejsc, które po prostu stwierdziły, że wiadomo, że P to podzbiór przecięcia NP i współ-NP. Dowody, które pokazują, że P jest podzbiorem NP, nie są trudne do znalezienia. Aby pokazać, że jest to podzbiór przecięcia, wszystko, co pozostało do zrobienia, pokazuje, że P jest podzbiorem współ-NP. Jaki może być tego dowód? Dziękuję bardzo!Dlaczego P ⊆ współ-NP?
Klasa P jest zamknięty pod uzupełnianie: jeśli L jest językiem w P, to dopełnienie L jest również w P. Możesz to zobaczyć, biorąc dowolny decydujący czas wielomianu dla L i przełączając stany przyjmowania i odrzucania; ta nowa maszyna decyduje teraz o uzupełnieniu L i robi to w czasie wielomianowym.
Język L jest pod numerem NP. Jego uzupełnienie to NP. Rozważmy dowolny język L ∈ P. Dopełnieniem L jest również w P tak dopełnieniem L jest zatem NP (ponieważ P i subseteq; NP). Dlatego L jest współ-NP. W konsekwencji, P i subseteq; co-NP.
Mam nadzieję, że to pomoże!
Pomyśl o tym w ten sposób. Rozważ klasę co-P. Ponieważ P jest zamknięte pod komplementem, P = co-P.
Powinno być również jasne, że co-P jest podzbiorem współ-NP, ponieważ P jest zawarty w NP. Ponieważ P = co-P, wynika, że P jest zawarte w co-NP.
Osobiście nie przeszkadza mi, że to pytanie jest zadawane tutaj, ale jeśli inni wyrażają sprzeciw, możesz również zadać pytanie na http://cs.stackexchange.com –
To pytanie wydaje się być nie na temat, ponieważ dotyczy matematyki –