Može li problem biti u klasi složenosti NP ako postoji nedeterministički turingov stroj koji će ga riješiti u polinomnom vremenu
Pitanje "Može li problem biti u klasi složenosti NP ako postoji nedeterministički Turingov stroj koji će ga riješiti u polinomnom vremenu?" dotiče se temeljnih pojmova u teoriji računalne složenosti. Kako bismo sveobuhvatno odgovorili na ovo pitanje, moramo razmotriti definicije i karakteristike klase složenosti NP i ulogu nedeterminističkih Turingovih strojeva (NDTM).
Definicija NP
Klasa NP (nedeterminističko polinomijalno vrijeme) sastoji se od problema odlučivanja za koje se dano rješenje može verificirati kao točno ili netočno u polinomijalnom vremenu determinističkim Turingovim strojem (DTM). Formalno, problem odlučivanja je u NP ako postoji algoritam provjere polinomnog vremena koji može provjeriti ispravnost danog certifikata (ili svjedoka) za instancu problema.
Nedeterministički Turingovi strojevi
Nedeterministički Turingov stroj je teorijski model računanja koji proširuje mogućnosti determinističkog Turingovog stroja. Za razliku od DTM-a, koji slijedi jedan računski put definiran njegovom prijelaznom funkcijom, NDTM može slijediti više računalnih putova istovremeno. U svakom koraku, NDTM može "birati" iz niza mogućih prijelaza, učinkovito paralelno istražujući mnoge moguće proračune.
Polinomska vremenska rješivost pomoću NDTM-ova
Kaže se da je problem rješiv pomoću NDTM-a u polinomnom vremenu ako postoji nedeterministički algoritam koji može pronaći rješenje problema unutar broja koraka koji je polinomijalan u veličini ulaza. To znači da za bilo koju instancu problema NDTM može istražiti računalni put koji vodi do rješenja u polinomnom vremenu.
Odnos između NP i NDTM
Klasa NP može se ekvivalentno definirati u terminima NDTM. Konkretno, problem odlučivanja je u NP ako i samo ako postoji NDTM koji može riješiti problem u polinomijalnom vremenu. Ova istovrijednost proizlazi iz činjenice da NDTM može pogoditi certifikat nedeterministički i zatim ga deterministički provjeriti u polinomijalnom vremenu.
Da bismo to ilustrirali primjerom, razmotrimo dobro poznati problem NP-potpunosti, Boolean problem zadovoljivosti (SAT). S obzirom na Booleovu formulu u konjunktivnom normalnom obliku (CNF), zadatak je utvrditi postoji li dodjela vrijednosti istine varijablama koja čini formulu istinitom. NDTM može riješiti SAT u polinomijalnom vremenu nedeterminističkim pogađanjem dodjele istinitih vrijednosti i zatim determinističkom provjerom zadovoljava li dodjela formulu. Korak provjere, koji uključuje procjenu formule pod pretpostavljenim dodjeljivanjem, može se obaviti u polinomnom vremenu.
Implikacije rješivosti polinomskog vremena pomoću NDTM-ova
S obzirom na gornje definicije i ekvivalentnost između NP i rješivosti u polinomnom vremenu pomoću NDTM-ova, možemo zaključiti da ako postoji NDTM koji rješava problem u polinomnom vremenu, onda je problem doista u NP. To je zato što postojanje takvog NDTM-a implicira da postoji algoritam verifikacije polinomnog vremena za problem. Faza nedeterminističkog pogađanja NDTM-a odgovara generiranju certifikata, a faza determinističke verifikacije odgovara algoritmu verifikacije u polinomnom vremenu.
Daljnja razmatranja i primjeri
Kako bismo dodatno razjasnili ovaj koncept, razmotrimo dodatne primjere problema u NP-u i njihov odnos s NDTM-ovima:
1. Hamiltonov problem puta: Za dan graf, problem Hamiltonovog puta postavlja pitanje postoji li put koji posjećuje svaki vrh točno jednom. NDTM može riješiti ovaj problem u polinomijalnom vremenu nedeterminističkim pogađanjem slijeda vrhova i zatim provjerom čini li slijed važeći Hamiltonov put. Korak provjere uključuje provjeru susjedstva uzastopnih vrhova i osiguravanje da je svaki vrh posjećen točno jednom, a oba se mogu obaviti u polinomnom vremenu.
2. Problem zbroja podskupa: Zadani su skup cijelih brojeva i ciljni zbroj, problem zbroja podskupa pita postoji li podskup cijelih brojeva koji zbraja cilj. NDTM može riješiti ovaj problem u polinomijalnom vremenu nedeterminističkim pogađanjem podskupa cijelih brojeva i zatim provjerom je li zbroj podskupa jednak cilju. Korak provjere uključuje zbrajanje elemenata pretpostavljenog podskupa, što se može učiniti u polinomnom vremenu.
3. Problem bojanja grafikona: S obzirom na graf i niz boja, problem bojanja grafa postavlja pitanje je li moguće obojiti vrhove grafa tako da nijedna dva susjedna vrha ne dijele istu boju. NDTM može riješiti ovaj problem u polinomnom vremenu nedeterminističkim dodjeljivanjem boja vrhovima i zatim provjerom je li bojanje valjano. Korak provjere uključuje provjeru boja susjednih vrhova, što se može učiniti u polinomnom vremenu.
Zaključak
U svjetlu navedenih definicija i primjera, jasno je da problem doista može biti u klasi složenosti NP ako postoji nedeterministički Turingov stroj koji će ga riješiti u polinomijalnom vremenu. Ovaj odnos kamen je temeljac teorije računalne složenosti i naglašava jednakost između rješivosti u polinomnom vremenu pomoću NDTM-ova i članstva 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?
- 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?
- Postoji li kontradikcija između definicije NP kao klase problema odlučivanja s verifikatorima polinomnog vremena i činjenice da problemi u klasi P također imaju verifikatore polinomnog vremena?
Više pitanja i odgovora pogledajte u Složenosti