U području teorije računalne složenosti, posebno kada se ispituju klase složenosti prostora, odnos između PSPACE i NP je od velikog interesa. Da izravno odgovorimo na pitanje: da, postoje problemi u PSPACE-u za koje ne postoji poznati NP algoritam. Ova tvrdnja je ukorijenjena u definicijama i odnosima između ovih klasa složenosti.
PSPACE je klasa problema odlučivanja koje može riješiti Turingov stroj pomoću polinomske količine prostora. Drugim riječima, problem je u PSPACE-u ako postoji algoritam koji ga može riješiti koristeći količinu memorije koja je polinomijalna u veličini ulaza. Ova klasa obuhvaća širok raspon problema, od kojih su neki prilično složeni i uključuju zamršene računalne procese.
NP je, s druge strane, klasa problema odlučivanja za koje se predloženo rješenje može verificirati u polinomnom vremenu determinističkim Turingovim strojem. To znači da ako vam netko pruži kandidatsko rješenje problema u NP-u, možete brzo provjeriti ispravnost tog rješenja, posebno u polinomnom vremenu u odnosu na veličinu ulaza.
Odnos između ove dvije klase je takav da je NP podskup PSPACE-a. To je zato što se svaki problem koji se može provjeriti u polinomnom vremenu također može riješiti u polinomnom prostoru. Da biste razumjeli zašto, uzmite u obzir da verifikator polinomnog vremena može pročitati samo polinomni broj bitova ulaza i predloženog rješenja. Stoga se može simulirati strojem za polinomski prostor koji prati položaje koje je pročitao i operacije koje je izvršio.
Međutim, nije poznato da je obrnuto točno; odnosno nije poznato da li je PSPACE podskup od NP. Zapravo, široko se vjeruje da PSPACE sadrži probleme koji nisu u NP, iako to nije službeno dokazano. Ovo se uvjerenje temelji na postojanju problema u PSPACE-u za koje se čini da zahtijevaju više od polinomskog vremena za rješavanje, iako se mogu riješiti s polinomnim prostorom.
Jedan od kanonskih primjera problema u PSPACE-u za koji se ne zna da postoji u NP je problem kvantificirane Booleove formule (QBF). QBF je generalizacija Booleovog problema zadovoljavanja (SAT), koji je NP-kompletan. Dok SAT pita postoji li dodjela vrijednosti istine varijablama koja čini danu Booleovu formulu istinitom, QBF uključuje ugniježđene kvantifikatore nad varijablama, kao što je "za sve x, postoji ay tako da je formula istinita." Prisutnost ovih kvantifikatora čini QBF znatno složenijim. QBF je kompletan za PSPACE, što znači da je težak kao bilo koji problem u PSPACE-u. Kad bi postojao NP algoritam za QBF, to bi značilo da je NP jednako PSPACE, rezultat koji bi bio revolucionaran i općenito se smatra malo vjerojatnim.
Još jedan ilustrativan primjer je problem određivanja pobjednika u generaliziranim igrama, kao što su generalizirane verzije šaha ili Go, koje se igraju na N x N ploči. Ovi problemi uključuju potencijalno eksponencijalni broj poteza i konfiguracija, ali se o njima može odlučiti pomoću prostora polinoma sustavnim istraživanjem svih mogućih stanja igre. Ovi problemi su također PSPACE-potpuni, što dalje sugerira postojanje problema u PSPACE-u koji nisu u NP-u.
Da bismo dublje istražili zašto se vjeruje da su određeni problemi u PSPACE-u izvan NP-a, razmotrite prirodu proračuna ograničenih prostorom u odnosu na vremenski ograničene. Polinomski prostor dopušta potencijalno eksponencijalni broj računskih koraka, sve dok korišteni prostor ostaje polinomski ograničen. Ovo je u oštroj suprotnosti s NP, gdje je vrijeme polinomski ograničeno. Eksponencijalno vrijeme dopušteno polinomskim prostorom može se iskoristiti za rješavanje problema koji uključuju iscrpna pretraživanja preko eksponencijalno velikih prostora, poput onih koji se susreću u QBF i generaliziranim igrama.
Štoviše, postoje zamršeni teorijski konstrukti koji dodatno podržavaju razliku između PSPACE i NP. Na primjer, koncept alternacije, koji su uveli Chandra, Kozen i Stockmeyer, generalizira nedeterminizam i vodi do klase AP (alternating polynomial time). Pokazalo se da je AP jednako PSPACE, čime se pruža drugačija perspektiva o snazi izračuna polinomskog prostora. Alternacija uključuje niz egzistencijalnih i univerzalnih kvantifikatora, odražavajući strukturu QBF-a, i prikazuje složenost svojstvenu PSPACE problemima.
Također je vrijedno napomenuti da je razdvajanje klasa složenosti temeljno otvoreno pitanje u teorijskoj informatičkoj znanosti. Poznati P vs NP problem poseban je slučaj ovog šireg istraživanja. Slično, pitanje je li NP jednako PSPACE ostaje neriješeno. Međutim, konsenzus na terenu, temeljen na opsežnoj studiji i prirodi poznatih problema, je da PSPACE vjerojatno sadrži probleme koji nisu u NP.
Postojanje problema u PSPACE-u za koje ne postoji poznati NP algoritam potkrijepljeno je definicijama i odnosima između ovih klasa složenosti, kao i konkretnim primjerima poput QBF-a i problema generaliziranih igara. Ovi primjeri naglašavaju zamršene i potencijalno eksponencijalne računske procese kojima se može upravljati unutar polinomijalnog prostora, ali je malo vjerojatno da će biti ograničeni na polinomijalno vrijeme, čime se stavljaju izvan područja 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?
- 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