Skaičiavimo sudėtingumo teorijos srityje, ypač nagrinėjant erdvės sudėtingumo klases, ryšys tarp PSPACE ir NP yra labai svarbus. Norėdami atsakyti į klausimą tiesiogiai: taip, PSPACE yra problemų, kurioms nėra žinomo NP algoritmo. Šis tvirtinimas grindžiamas šių sudėtingumo klasių apibrėžimais ir ryšiais.
PSPACE yra sprendimų problemų klasė, kurią gali išspręsti Turingo mašina, naudodama daugianarį erdvės kiekį. Kitaip tariant, problema yra PSPACE, jei yra algoritmas, galintis ją išspręsti naudojant atminties kiekį, kuris yra daugianario įvesties dydžio. Ši klasė apima daugybę problemų, kai kurios iš jų yra gana sudėtingos ir susijusios su sudėtingais skaičiavimo procesais.
Kita vertus, NP yra sprendimų problemų klasė, kurios pasiūlytą sprendimą polinominiu laiku galima patikrinti deterministine Tiuringo mašina. Tai reiškia, kad jei kas nors pateikia jums galimą NP problemos sprendimą, galite greitai patikrinti to sprendimo teisingumą, ypač daugianario laiku, palyginti su įvesties dydžiu.
Ryšys tarp šių dviejų klasių yra toks, kad NP yra PSPACE poaibis. Taip yra todėl, kad bet kokia problema, kurią galima patikrinti daugianario laiku, taip pat gali būti išspręsta daugianario erdvėje. Norėdami suprasti, kodėl, apsvarstykite, kad daugianario laiko tikrintuvas gali nuskaityti tik polinominį įvesties bitų skaičių ir siūlomą sprendimą. Todėl jį galima imituoti daugianario erdvės mašina, kuri seka perskaitytas pozicijas ir atliktas operacijas.
Tačiau žinoma, kad priešingai nėra; tai yra, nėra žinoma, ar PSPACE yra NP poaibis. Tiesą sakant, plačiai manoma, kad PSPACE yra problemų, kurių nėra NP, nors tai nebuvo oficialiai įrodyta. Šis įsitikinimas grindžiamas PSPACE problemų, kurioms išspręsti, atrodo, reikia daugiau nei daugianario laiko, buvimu, nors jas galima išspręsti naudojant daugianario erdvę.
Vienas iš kanoninių PSPACE problemos, kuri, kaip žinoma, nėra NP, pavyzdžių, yra kiekybinės Būlio formulės (QBF) problema. QBF yra Būlio patenkinimo problemos (SAT) apibendrinimas, kuris yra visiškai NP. Nors SAT klausia, ar yra tiesos reikšmių priskyrimas kintamiesiems, dėl kurių tam tikra Būlio formulė yra teisinga, QBF apima įdėtus kvantorius virš kintamųjų, pvz., „visiems x yra ay, kad formulė būtų teisinga“. Šių kvantiklių buvimas daro QBF žymiai sudėtingesnį. QBF yra pilnas PSPACE, tai reiškia, kad tai taip pat sunku, kaip ir bet kokia PSPACE problema. Jei būtų QBF NP algoritmas, tai reikštų, kad NP yra lygus PSPACE, o rezultatas būtų novatoriškas ir plačiai laikomas mažai tikėtinu.
Kitas iliustruojantis pavyzdys yra nugalėtojo nustatymo problema apibendrintuose žaidimuose, tokiuose kaip apibendrintos šachmatų ar „Go“ versijos, žaidžiamos ant N x N lentos. Šios problemos apima potencialiai eksponentinį judesių ir konfigūracijų skaičių, tačiau jas galima išspręsti naudojant polinominę erdvę, sistemingai tyrinėjant visas galimas žaidimo būsenas. Šios problemos taip pat yra visiškai PSPACE, o tai dar labiau rodo, kad PSPACE yra problemų, kurių nėra NP.
Norėdami giliau įsigilinti į tai, kodėl manoma, kad tam tikros problemos PSPACE yra už NP ribų, apsvarstykite erdvės ir laiko apribotų skaičiavimų pobūdį. Polinominė erdvė leidžia atlikti potencialiai eksponentinį skaičiavimo žingsnių skaičių, jei naudojama erdvė išlieka polinomiškai apribota. Tai visiškai prieštarauja NP, kur laikas yra ribojamas polinomiškai. Eksponentinis laikas, kurį leidžia daugianario erdvė, gali būti panaudotas sprendžiant problemas, susijusias su išsamia paieška eksponentiškai didelėse erdvėse, pvz., QBF ir apibendrintuose žaidimuose.
Be to, yra sudėtingų teorinių konstrukcijų, kurios dar labiau palaiko skirtumą tarp PSPACE ir NP. Pavyzdžiui, Chandra, Kozen ir Stockmeyer pristatyta kintamumo sąvoka apibendrina nedeterminizmą ir veda į AP klasę (kintamasis daugianario laikas). Buvo įrodyta, kad AP yra lygus PSPACE, taigi suteikiama kitokia perspektyva į daugianario erdvės skaičiavimo galią. Alternatyva apima egzistencinių ir universalių kvantiklių seką, atspindinčią QBF struktūrą ir parodo sudėtingumą, būdingą PSPACE problemoms.
Taip pat verta paminėti, kad sudėtingumo klasių atskyrimas yra esminis atviras teorinės kompiuterių mokslo klausimas. Garsioji P vs NP problema yra ypatingas šio platesnio tyrimo atvejis. Panašiai lieka neišspręstas klausimas, ar NP lygus PSPACE. Tačiau sutarimas šioje srityje, pagrįstas išsamiais tyrimais ir žinomų problemų pobūdžiu, yra tas, kad PSPACE greičiausiai yra problemų, kurių nėra NP.
PSPACE problemų, kurioms nėra žinomo NP algoritmo, egzistavimą patvirtina apibrėžimai ir ryšiai tarp šių sudėtingumo klasių, taip pat konkretūs pavyzdžiai, tokie kaip QBF ir apibendrintos žaidimo problemos. Šie pavyzdžiai pabrėžia sudėtingus ir potencialiai eksponentinius skaičiavimo procesus, kurie gali būti valdomi polinominėje erdvėje, bet vargu ar apsiriboja polinominiu laiku, todėl jie yra už NP srities.
Kiti naujausi klausimai ir atsakymai apie sudėtingumas:
- Ar PSPACE klasė nėra lygi EXPSPACE klasei?
- Ar P sudėtingumo klasė yra PSPACE klasės poaibis?
- Ar galime įrodyti, kad Np ir P klasės yra vienodos, rasdami veiksmingą daugianario sprendimą bet kuriai NP užbaigtai problemai deterministinėje TM?
- Ar NP klasė gali būti lygi EXPTIME klasei?
- Ar SAT problema gali būti visiška NP problema?
- Ar problema gali būti NP sudėtingumo klasėje, jei yra nedeterministinė tiūro mašina, kuri ją išspręs daugianario laiku
- NP yra kalbų, turinčių daugianario laiko tikrintuvus, klasė
- Ar iš tikrųjų P ir NP yra ta pati sudėtingumo klasė?
- Ar P sudėtingumo klasėje kiekviena kalba be konteksto?
- Ar yra prieštaravimas tarp NP apibrėžimo kaip sprendimų problemų klasės, naudojant daugianario laiko tikrintuvus, ir to, kad P klasės uždaviniai taip pat turi daugianario laiko tikrintuvus?
Peržiūrėkite daugiau klausimų ir atsakymų skyriuje „Sudėtingumas“.