Može li klasa NP biti jednaka klasi EXPTIME?
Pitanje može li klasa NP biti jednaka klasi EXPTIME zadire u temeljne aspekte teorije računalne složenosti. Kako bismo sveobuhvatno odgovorili na ovaj upit, bitno je razumjeti definicije i svojstva ovih klasa složenosti, odnose među njima i implikacije takve jednakosti.
Definicije i svojstva
NP (nedeterminističko polinomsko vrijeme):
Klasa NP sastoji se od problema odlučivanja za koje se dano rješenje može verificirati kao točno ili netočno u polinomnom vremenu determinističkim Turingovim strojem. Formalno, jezik ( L ) je u NP ako postoji polinomski verifikator vremena ( V ) i polinom ( p ) tako da za svaki niz ( x u L ), postoji certifikat ( y ) s ( |y| leq p(|x|)) i (V(x, y) = 1).
EXPTIME (eksponencijalno vrijeme):
Klasa EXPTIME uključuje probleme odlučivanja koji se mogu riješiti determinističkim Turingovim strojem u eksponencijalnom vremenu. Formalno, jezik ( L ) je u EXPTIME ako postoji deterministički Turingov stroj ( M ) i konstanta ( k ) takva da za svaki niz ( x u L ), ( M ) odlučuje ( x ) u vremenu ( O(2 ^{n^k}) ), gdje je ( n ) duljina ( x ).
Odnos između NP i EXPTIME
Da bismo analizirali može li NP biti jednako EXPTIME, moramo razmotriti poznate odnose između ovih klasa i implikacije takve jednakosti.
1. Zadržavanje:
Poznato je da se NP nalazi unutar EXPTIME. To je zato što se bilo koji problem koji se može provjeriti u polinomijalnom vremenu (kao u NP) također može riješiti u eksponencijalnom vremenu. Konkretno, nedeterministički polinomski algoritam vremena može se simulirati determinističkim eksponencijalnim vremenskim algoritmom. Stoga, ( text{NP} subseteq text{EXPTIME} ).
2. odvajanje:
Široko rasprostranjeno uvjerenje u teoriji složenosti je da je NP strogo sadržan unutar EXPTIME, tj. ( text{NP} subsetneq text{EXPTIME}). Ovo uvjerenje proizlazi iz činjenice da su NP problemi rješivi u nedeterminističkom polinomijalnom vremenu, koje se općenito smatra manjom klasom od problema rješivih u determinističkom eksponencijalnom vremenu.
Implikacije NP = EXPTIME
Kad 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 polinomijalnom vremenu. To bi impliciralo da se mnogi problemi za koje se trenutačno smatra da zahtijevaju eksponencijalno vrijeme mogu umjesto toga biti verificirani (a time i potencijalno riješeni) u polinomijalnom vremenu, što je u suprotnosti s trenutnim uvjerenjima u teoriji složenosti.
2. Sažimanje klasa složenosti:
Kad bi NP bilo jednako EXPTIME, to bi također impliciralo kolaps nekoliko klasa složenosti. Na primjer, to bi impliciralo da ( tekst {P} = tekst {NP} ), jer bi NP-kompletni problemi bili rješivi u polinomnom vremenu. To bi dalje impliciralo da je ( text{P} = text{PSPACE} ), i potencijalno dovelo do kolapsa hijerarhije polinoma.
Primjeri i daljnja razmatranja
Za ilustraciju implikacija, razmotrite sljedeće primjere:
1. SAT (problem zadovoljavanja):
SAT je dobro poznati NP-kompletan problem. Kad bi NP bio jednak EXPTIME, to bi značilo da se SAT može riješiti u determinističkom eksponencijalnom vremenu. Još značajnije, to bi impliciralo da se SAT može provjeriti u polinomijalnom vremenu i stoga riješiti u polinomijalnom vremenu, što dovodi do (tekst{P} = tekst{NP}).
2. Šah:
Poznato je da je problem utvrđivanja ima li igrač pobjedničku strategiju u danoj šahovskoj poziciji EXPTIME. Kad bi NP bilo jednako EXPTIME, to bi impliciralo da se takav problem može provjeriti u polinomnom vremenu, što se trenutno ne vjeruje da je moguće.
Zaključak
Pitanje može li klasa NP biti jednaka klasi EXPTIME značajno je u teoriji računalne složenosti. Na temelju trenutnog znanja, vjeruje se da je NP strogo sadržan unutar EXPTIME. Implikacije da je NP jednako EXPTIME bile bi duboke, dovele bi do kolapsa nekoliko klasa složenosti i dovele bi u pitanje naše trenutno razumijevanje polinomnog naspram eksponencijalnog vremena.
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?
- 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?
- 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