Kako se polinomski verifikator vremena može pretvoriti u ekvivalentnu nedeterminističku Turingovu mašinu?
Verifikator polinomskog vremena može se pretvoriti u ekvivalentnu nedeterminističku Turingovu mašinu konstruisanjem mašine koja može pogoditi sertifikat dokaza i verificirati ga u polinomskom vremenu. Ova konverzija je zasnovana na konceptu nedeterminističkog izračunavanja, koji omogućava mašini da istovremeno istražuje sve moguće puteve.
Da bismo razumjeli ovu konverziju, hajde da prvo definiramo šta je polinomski verifikator vremena. U teoriji složenosti računanja, verifikator polinomskog vremena je deterministička Turingova mašina koja može provjeriti ispravnost rješenja problema odlučivanja u polinomskom vremenu. Potrebna su dva ulaza: instanca problema i potvrda dokaza i određuje da li je certifikat valjani dokaz za datu instancu.
Sada, da bismo pretvorili polinomski verifikator vremena u ekvivalentnu nedeterminističku Turingovu mašinu, moramo razmotriti svojstva nedeterminističkog izračunavanja. U nedeterminističkoj Turing mašini, na svakom koraku, mašina može biti u više stanja i može preći u više stanja istovremeno. Ovo omogućava mašini da istražuje sve moguće puteve računanja paralelno.
Da bismo konvertovali verifikator, možemo konstruisati nedeterminističku Turingovu mašinu koja pogađa sertifikat dokaza i zatim simulira verifikator na svim mogućim putevima. Ako bilo koji od puteva prihvati, onda nedeterministička mašina prihvata. U suprotnom, odbija.
Ilustrirajmo to primjerom. Pretpostavimo da imamo polinomski verifikator vremena za problem bojenja grafa. Verifikator uzima kao ulaz graf i boju njegovih vrhova, i provjerava da li je bojanje važeća provjeravajući da nijedan susjedni vrh nema istu boju.
Da bismo ovaj verifikator pretvorili u nedeterminističku Turingovu mašinu, konstruišemo mašinu koja pogađa boju i zatim simulira verifikator na svim mogućim bojama istovremeno. Ako bilo koje od boja zadovoljava ograničenja bojenja, onda nedeterministička mašina prihvata. U suprotnom, odbija.
U ovom primjeru, nedeterministička mašina bi pogodila boju tako što bi paralelno dodijelila boje vrhovima. Zatim bi simulirao verifikator na svakoj od mogućih boja, provjeravajući da li je boja valjana. Ako bilo koja od simulacija prihvati, onda nedeterministička mašina prihvata.
Koristeći ovu konverziju, možemo vidjeti da se polinomski verifikator vremena može pretvoriti u ekvivalentnu nedeterminističku Turingovu mašinu. Ova konverzija nam omogućava da analiziramo složenost problema u klasi NP (nedeterminističko polinomno vrijeme) uzimajući u obzir postojanje verifikatora polinomskog vremena.
Polinomski verifikator vremena može se pretvoriti u ekvivalentnu nedeterminističku Turingovu mašinu konstruisanjem mašine koja pogađa sertifikat dokaza i verifikuje ga na svim mogućim putanjama istovremeno. Ova konverzija nam omogućava da analiziramo složenost problema u klasi NP.
Ostala nedavna pitanja i odgovori u vezi složenost:
- Zar PSPACE klasa nije jednaka klasi EXPSPACE?
- Da li je P klasa složenosti podskup klase PSPACE?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem efikasnog polinomskog rješenja za bilo koji NP kompletan problem na determinističkom TM?
- Može li NP klasa biti jednaka klasi EXPTIME?
- Postoje li problemi u PSPACE-u za koje ne postoji poznati NP algoritam?
- Može li SAT problem biti NP potpuni problem?
- Može li problem biti u klasi složenosti NP ako postoji nedeterministička Turingova mašina koja će ga riješiti u polinomskom vremenu
- NP je klasa jezika koji imaju verifikatore polinomskog vremena
- Da li su P i NP zapravo ista klasa složenosti?
- Da li je svaki jezik bez konteksta u P klasi složenosti?
Pogledajte više pitanja i odgovora u Complexity