Kako se polinomski verifikator vremena može pretvoriti u ekvivalentni nedeterministički Turingov stroj?
Polinomijalni vremenski verifikator može se pretvoriti u ekvivalentni nedeterministički Turingov stroj konstruiranjem stroja koji može pogoditi dokazni certifikat i provjeriti ga u polinomijalnom vremenu. Ova se pretvorba temelji na konceptu nedeterminističkog izračuna, koji omogućuje stroju da istovremeno istražuje sve moguće staze.
Da bismo razumjeli ovu konverziju, prvo definirajmo što je verifikator vremena polinoma. U teoriji računalne složenosti, verifikator polinomnog vremena je deterministički Turingov stroj koji može provjeriti točnost rješenja problema odlučivanja u polinomnom vremenu. Potrebna su dva ulaza: instanca problema i potvrda dokaza te se utvrđuje je li potvrda važeći dokaz za danu instancu.
Sada, da bismo pretvorili polinomski verifikator vremena u ekvivalentni nedeterministički Turingov stroj, moramo uzeti u obzir svojstva nedeterminističkog izračuna. U nedeterminističkom Turingovom stroju, u svakom koraku, stroj može biti u više stanja i može prijeći u više stanja istovremeno. To omogućuje stroju da paralelno istražuje sve moguće putove računanja.
Kako bismo pretvorili verifikator, možemo konstruirati nedeterministički Turingov stroj koji pogađa dokazni certifikat i zatim simulira verifikator na svim mogućim putevima. Ako bilo koji od putova prihvati, tada nedeterministički stroj prihvaća. U suprotnom, odbija.
Ilustrirajmo to primjerom. Pretpostavimo da imamo polinomski verifikator vremena za problem bojanja grafa. Verifikator kao ulaz uzima graf i bojanje njegovih vrhova, te provjerava je li bojanje valjano provjerom da nijedan susjedni vrh nema istu boju.
Kako bismo ovaj verifikator pretvorili u nedeterministički Turingov stroj, konstruiramo stroj koji pogađa boju i zatim simulira verifikator na svim mogućim bojama istovremeno. Ako bilo koje od bojanja zadovoljava ograničenja bojanja, tada nedeterministički stroj prihvaća. U suprotnom, odbija.
U ovom primjeru, nedeterministički stroj bi pogodio boju paralelnim dodjeljivanjem boja vrhovima. Zatim bi simulirao verifikator na svakoj od mogućih boja, provjeravajući je li boja valjana. Ako bilo koja od simulacija prihvati, tada nedeterministički stroj prihvaća.
Korištenjem ove pretvorbe možemo vidjeti da se polinomski verifikator vremena može pretvoriti u ekvivalentan nedeterministički Turingov stroj. Ova nam konverzija omogućuje analizu složenosti problema u klasi NP (nedeterminističko polinomno vrijeme) uzimajući u obzir postojanje polinomnih verifikatora vremena.
Polinomijalni vremenski verifikator može se pretvoriti u ekvivalentni nedeterministički Turingov stroj konstruiranjem stroja koji pogađa dokazni certifikat i provjerava ga na svim mogućim stazama istovremeno. Ova nam konverzija omogućuje analizu složenosti problema u klasi NP.
Ostala nedavna pitanja i odgovori u vezi Složenost:
- Nije li klasa PSPACE jednaka klasi EXPSPACE?
- Je li P klasa složenosti podskup PSPACE klase?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem učinkovitog polinomskog rješenja za bilo koji NP potpuni problem na determinističkom TM?
- Može li klasa NP biti jednaka klasi EXPTIME?
- Postoje li problemi u PSPACE-u za koje ne postoji poznati NP algoritam?
- Može li problem SAT biti potpuni problem NP?
- Može li problem biti u klasi složenosti NP ako postoji nedeterministički turingov stroj koji će ga riješiti u polinomnom vremenu
- NP je klasa jezika koji imaju polinomske verifikatore vremena
- Jesu li P i NP zapravo ista klasa složenosti?
- Je li svaki kontekstno slobodni jezik u P klasi složenosti?
Više pitanja i odgovora pogledajte u Složenosti