Vyskytujú sa v PSPACE problémy, pre ktoré nie je známy NP algoritmus?
V oblasti teórie výpočtovej zložitosti, najmä pri skúmaní tried priestorovej zložitosti, je vzťah medzi PSPACE a NP veľmi zaujímavý. Aby som odpovedal priamo na otázku: áno, v PSPACE sú problémy, pre ktoré nie je známy NP algoritmus. Toto tvrdenie je zakorenené v definíciách a vzťahoch medzi týmito triedami zložitosti.
PSPACE je trieda rozhodovacích problémov, ktoré je možné vyriešiť pomocou Turingovho stroja pomocou polynomického priestoru. Inými slovami, problém je v PSPACE, ak existuje algoritmus, ktorý ho dokáže vyriešiť pomocou množstva pamäte, ktorá je polynomická vo veľkosti vstupu. Táto trieda zahŕňa širokú škálu problémov, z ktorých niektoré sú dosť zložité a zahŕňajú zložité výpočtové procesy.
NP, na druhej strane, je trieda rozhodovacích problémov, pre ktoré môže byť navrhované riešenie overené v polynomiálnom čase deterministickým Turingovým strojom. To znamená, že ak vám niekto poskytne kandidátne riešenie problému v NP, môžete rýchlo skontrolovať správnosť tohto riešenia, konkrétne v polynomickom čase vzhľadom na veľkosť vstupu.
Vzťah medzi týmito dvoma triedami je taký, že NP je podmnožinou PSPACE. Je to preto, že každý problém, ktorý sa dá overiť v polynomiálnom čase, sa dá vyriešiť aj v polynomickom priestore. Aby ste pochopili prečo, zvážte, že polynómový verifikátor dokáže prečítať iba polynómový počet bitov vstupu a navrhovaného riešenia. Preto môže byť simulovaný strojom s polynomickým priestorom, ktorý sleduje pozície, ktoré načítal, a operácie, ktoré vykonal.
Nie je však známe, že opak je pravdou; to znamená, že nie je známe, či PSPACE je podmnožinou NP. V skutočnosti sa všeobecne verí, že PSPACE obsahuje problémy, ktoré nie sú v NP, hoci to nebolo formálne dokázané. Toto presvedčenie je založené na existencii problémov v PSPACE, ktorých vyriešenie si zrejme vyžaduje viac ako polynómny čas, aj keď je možné ich vyriešiť pomocou polynomického priestoru.
Jedným z kanonických príkladov problému v PSPACE, o ktorom nie je známe, že je v NP, je problém s kvantifikovaným booleovským vzorcom (QBF). QBF je zovšeobecnením boolovského problému splniteľnosti (SAT), ktorý je NP-úplný. Zatiaľ čo SAT sa pýta, či existuje priradenie pravdivostných hodnôt k premenným, ktoré robí daný booleovský vzorec pravdivým, QBF zahŕňa vnorené kvantifikátory nad premennými, ako napríklad "pre všetky x existuje taká, že vzorec je pravdivý." Prítomnosť týchto kvantifikátorov robí QBF výrazne zložitejším. QBF je úplný PSPACE, čo znamená, že je taký ťažký ako akýkoľvek problém v PSPACE. Ak by existoval NP algoritmus pre QBF, znamenalo by to, že NP sa rovná PSPACE, čo je výsledok, ktorý by bol prelomový a všeobecne sa považuje za nepravdepodobný.
Ďalším názorným príkladom je problém určenia víťaza v zovšeobecnených hrách, ako sú zovšeobecnené verzie šachu alebo Go, hrané na šachovnici N x N. Tieto problémy zahŕňajú potenciálne exponenciálny počet ťahov a konfigurácií, ale možno ich vyriešiť pomocou polynomiálneho priestoru systematickým skúmaním všetkých možných herných stavov. Tieto problémy sú tiež úplné v PSPACE, čo ďalej naznačuje existenciu problémov v PSPACE, ktoré nie sú v NP.
Ak sa chcete hlbšie ponoriť do toho, prečo sa predpokladá, že určité problémy v PSPACE sú mimo NP, zvážte povahu výpočtov ohraničených priestorom verzus časovo ohraničených. Polynomiálny priestor umožňuje potenciálne exponenciálny počet výpočtových krokov, pokiaľ použitý priestor zostáva polynomiálne ohraničený. To je v ostrom kontraste s NP, kde je čas polynomiálne ohraničený. Exponenciálny čas, ktorý umožňuje polynomický priestor, možno využiť na riešenie problémov, ktoré zahŕňajú vyčerpávajúce vyhľadávanie v exponenciálne veľkých priestoroch, ako sú tie, ktoré sa vyskytujú v QBF a všeobecných hrách.
Okrem toho existujú zložité teoretické konštrukty, ktoré ďalej podporujú rozdiel medzi PSPACE a NP. Napríklad koncept alternácie, ktorý zaviedli Chandra, Kozen a Stockmeyer, zovšeobecňuje nedeterminizmus a vedie k triede AP (alternujúci polynómový čas). Ukázalo sa, že AP sa rovná PSPACE, čím poskytuje iný pohľad na silu výpočtov polynomiálneho priestoru. Alternácia zahŕňa sekvenciu existenciálnych a univerzálnych kvantifikátorov, ktoré odzrkadľujú štruktúru QBF a ukazuje zložitosť, ktorá je vlastná problémom PSPACE.
Za zmienku tiež stojí, že oddelenie tried zložitosti je základnou otvorenou otázkou v teoretickej informatike. Známy problém P vs NP je špeciálnym prípadom tohto širšieho skúmania. Podobne zostáva nevyriešená otázka, či sa NP rovná PSPACE. Avšak konsenzus v tejto oblasti, založený na rozsiahlej štúdii a povahe známych problémov, je taký, že PSPACE pravdepodobne obsahuje problémy, ktoré nie sú v NP.
Existencia problémov v PSPACE, pre ktoré nie je známy NP algoritmus, je podporená definíciami a vzťahmi medzi týmito triedami zložitosti, ako aj konkrétnymi príkladmi ako QBF a zovšeobecnené herné problémy. Tieto príklady zdôrazňujú zložité a potenciálne exponenciálne výpočtové procesy, ktoré je možné spravovať v polynomiálnom priestore, ale je nepravdepodobné, že by sa obmedzili na polynomiálny čas, čím sa umiestňujú mimo oblasť NP.
Ďalšie nedávne otázky a odpovede týkajúce sa zložitosť:
- Nerovná sa trieda PSPACE triede EXPSPACE?
- Je trieda zložitosti P podmnožinou triedy PSPACE?
- Môžeme dokázať, že Np a P trieda sú rovnaké nájdením efektívneho polynomického riešenia pre akýkoľvek NP úplný problém na deterministickom TM?
- Môže sa trieda NP rovnať triede EXPTIME?
- Môže byť problém SAT úplným problémom NP?
- Môže byť problém v triede zložitosti NP, ak existuje nedeterministický Turingov stroj, ktorý ho vyrieši v polynomiálnom čase
- NP je trieda jazykov, ktoré majú polynomiálne časové overovače
- Sú P a NP vlastne rovnaká trieda zložitosti?
- Je každý jazyk bez kontextu v triede zložitosti P?
- Existuje rozpor medzi definíciou NP ako triedy rozhodovacích problémov s polynomiálnymi verifikátormi a skutočnosťou, že problémy v triede P majú aj polynomiálne verifikátory?
Pozrite si ďalšie otázky a odpovede v časti Zložitosť