Pitanje da li NP klasa može biti jednaka klasi EXPTIME zadire u temeljne aspekte teorije računske složenosti. Da bismo sveobuhvatno odgovorili na ovaj upit, neophodno je razumjeti definicije i svojstva ovih klasa složenosti, odnose između njih i implikacije takve jednakosti.
Definicije i svojstva
NP (nedeterminističko polinomsko vrijeme):
Klasa NP se sastoji od problema odlučivanja za koje se dato rješenje može provjeriti kao ispravno ili netačno u polinomskom vremenu pomoću determinističke Turingove mašine. Formalno, jezik ( L ) je u NP ako postoji verifikator polinomskog vremena ( V ) i polinom ( p ) takvi da za svaki niz ( x u L ) postoji sertifikat ( y ) sa ( |y| leq p(|x|) ) i ( V(x, y) = 1).
EXPTIME (eksponencijalno vrijeme):
Klasa EXPTIME uključuje probleme odlučivanja koje može riješiti deterministička Turingova mašina u eksponencijalnom vremenu. Formalno, jezik ( L ) je u EXPTIME ako postoji deterministička Turingova mašina ( M ) i konstanta ( k ) takve da za svaki niz ( x u L ) ( M ) odlučuje ( x ) u vremenu ( O(2 ^{n^k}) ), gdje je (n) dužina (x).
Odnos između NP i EXPTIME
Da bismo analizirali da li NP može biti jednak EXPTIME, moramo razmotriti poznate odnose između ovih klasa i implikacije takve jednakosti.
1. Zadržavanje:
Poznato je da je NP sadržan u EXPTIME-u. To je zato što se svaki problem koji se može provjeriti u polinomskom vremenu (kao u NP) također može riješiti u eksponencijalnom vremenu. Konkretno, nedeterministički algoritam polinomskog vremena može se simulirati determinističkim algoritmom eksponencijalnog vremena. Dakle, (tekst{NP} podsetq tekst{EXPTIME}).
2. Razdvajanje:
Široko prihvaćeno vjerovanje u teoriju složenosti je da je NP striktno sadržan u EXPTIME, tj. (text{NP} subsetneq text{EXPTIME}). Ovo uvjerenje proizlazi iz činjenice da su NP problemi rješivi u nedeterminističkom polinomskom vremenu, koje se općenito smatra manjom klasom od problema rješivih u determinističkom eksponencijalnom vremenu.
Implikacije NP = EXPTIME
Kada bi NP bio jednak EXPTIME, to bi impliciralo nekoliko dubokih posljedica za naše razumijevanje računske složenosti:
1. Polinom u odnosu na eksponencijalno vrijeme:
Jednakost (text{NP} = text{EXPTIME}) bi sugerirala da se svaki problem koji se može riješiti u eksponencijalnom vremenu također može provjeriti u polinomskom vremenu. To bi impliciralo da bi mnogi problemi za koje se trenutno smatra da zahtijevaju eksponencijalno vrijeme mogli biti provjereni (i time potencijalno riješeni) u polinomskom vremenu, što je u suprotnosti sa trenutnim vjerovanjima u teoriju složenosti.
2. Kolaps klasa složenosti:
Kada bi NP bio jednak EXPTIME, to bi također impliciralo kolaps nekoliko klasa složenosti. Na primjer, to bi impliciralo da (tekst{P} = tekst{NP}), jer bi NP-potpuni problemi bili rješivi u polinomskom vremenu. Ovo bi dalje impliciralo da (text{P} = text{PSPACE}), i potencijalno dovelo do kolapsa polinomske hijerarhije.
Primjeri i dalja razmatranja
Da biste ilustrirali implikacije, razmotrite sljedeće primjere:
1. SAT (Problem sa zadovoljstvom):
SAT je dobro poznati NP-kompletan problem. Kada bi NP bio jednak EXPTIME, to bi impliciralo da se SAT može riješiti u determinističkom eksponencijalnom vremenu. Još značajnije, to bi impliciralo da se SAT može verificirati u polinomskom vremenu i tako riješiti u polinomskom vremenu, što dovodi do (tekst{P} = tekst{NP}).
2. Šah:
Poznato je da je problem određivanja da li igrač ima pobjedničku strategiju u datoj šahovskoj poziciji u EXPTIME. Kada bi NP bio jednak EXPTIME, to bi impliciralo da bi se takav problem mogao provjeriti u polinomskom vremenu, za što se trenutno vjeruje da nije moguće.
zaključak
Pitanje da li NP klasa može biti jednaka klasi EXPTIME je značajno u teoriji računske složenosti. Na osnovu trenutnog saznanja, vjeruje se da je NP striktno sadržan u EXPTIME-u. Implikacije da je NP jednak EXPTIME bile bi duboke, što bi dovelo do kolapsa nekoliko klasa složenosti i dovela u pitanje naše trenutno razumijevanje polinoma naspram eksponencijalnog vremena.
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?
- 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?
- Postoji li kontradikcija između definicije NP kao klase problema odlučivanja s verifikatorima polinomskog vremena i činjenice da problemi u klasi P također imaju verifikatore polinomskog vremena?
Pogledajte više pitanja i odgovora u Complexity