Přeskočit na obsah

PSPACE

Z Wikipedie, otevřené encyklopedie

PSPACE je v teorii složitosti množina všech rozhodovacích problémů, které lze vyřešit Turingovým strojem používajícím polynomiálně omezené množství paměti.[1][2][3]

Formální definice

[editovat | editovat zdroj]

Pokud označíme SPACE(t(n)) množinu všech problémů, které lze vyřešit Turingovým strojem používajícím prostor O(t(n)) pro nějakou funkci t vstupní velikosti n, pak můžeme definovat třídu úloh PSPACE formálně takto:[4]

PSPACE je ostrá nadmnožina množiny kontextových jazyků.

Ukazuje se, že povolením, aby Turingův stroj byl nedeterministický se nezíská žádná významná výhoda. Je to díky Savitchově větě,[5] NPSPACE je ekvivalentní s PSPACE v zásadě proto, že deterministický Turingův stroj může simulovat nedeterministický Turingův stroj, aniž by bylo potřeba mnohem více prostoru (může však potřebovat mnohem více času).[6] Také komplementy všech problémů v PSPACE jsou také v PSPACE, což znamená, že co-PSPACE = PSPACE.

Relace mezi jinými třídami

[editovat | editovat zdroj]
Reprezentace relací mezi třídami složitosti

Je známo, že platí následující relace mezi PSPACE a třídami složitost NL, P, NP, PH, EXPTIME a EXPSPACE (symbol ⊊, znamenající ostrou inkluzi, není totéž jako ⊈):

Z třetího řádku plyne, že v prvním i ve druhém řádku musí být alespoň jedna množinová inkluze ostrá, ale není známo která. Obecně se předpokládá, že jsou ostré všechny.

O inkluzích ve třetím řádku se ví, že jsou ostré. První vyplývá z přímé diagonalizace (věta o hierarchii prostorové složitosti, NL ⊊ NPSPACE) a faktu, že PSPACE = NPSPACE díky Savitchově větě. Druhá plyne jednoduše z věty o hierarchii prostorové složitosti.

Nejtěžší problémy v PSPACE jsou PSPACE-úplné problémy. V článku PSPACE-úplnost jsou uvedeny příklady problémů, o kterých se předpokládá, že jsou v PSPACE ale nejsou v NP.

Uzávěrové vlastnosti

[editovat | editovat zdroj]

Třída PSPACE je uzavřená vůči operaci sjednocení, množinového doplňku a Kleeneho hvězdičky.

Jiné charakterizace

[editovat | editovat zdroj]

Alternativní charakterizací PSPACE je množina problémů rozhodnutelných alternujícím Turingovým strojem v polynomiálním čase, někdy nazývaný APTIME nebo pouze AP.[7]

Logická charakterizace PSPACE z teorie deskriptivní složitosti je, že je to množina problémů vyjadřitelných v logice druhého řádu s přidáným operátorem tranzitivního uzávěru. Není potřeba plný tranzitivní uzávěr; postačuje komutativní tranzitivní uzávěr nebo dokonce slabší formy. Právě přidání tohoto operátoru (případně) rozlišuje PSPACE z PH.

Hlavním výsledkem teorie složitost je, že PSPACE lze charakterizovat jako všechny jazyky rozpoznávané určitým interaktivním dokazovacím systémem, tím, který definuje třídu IP. V tomto systému existuje dokazovací stroj všechno-výkonný, který přesvědčuje pravděpodobnostní verifikátor pracující v polynomiálním čase, že řetězec je v jazyce. Měl by být schopen s vysokou pravděpodobností přesvědčit verififikátor, že řetězec je v jazyce, ale neměl by být schopen jej přesvědčit (až na nízkou pravděpodobnost), že řetězec v jazyce není.

PSPACE lze charakterizovat jako kvantovou třídu složitosti QIP.[8]

PSPACE je také rovno PCTC, problémů řešitelných klasickými počítači používajícím uzavřených časupodobných křivek,[9] i BQPCTC, problémů řešitelných kvantovými počítači používajícím uzavřených časupodobných křivek.[10]

PSPACE-úplnost

[editovat | editovat zdroj]
Podrobnější informace naleznete v článku PSPACE-complete.

Jazyk B je PSPACE-úplný, pokud je v PSPACE a je PSPACE-těžký, což znamená, že pro všechno A ∈ PSPACE, , kde znamená, že existuje redukce z mnoha na jeden v polynomiálním čase z A do B. PSPACE-úplné problémy mají velký význam pro studium PSPACE problémů, protože reprezentují nejobtížnější problémy v PSPACE. Naleznutí jednoduchého řešení nějakého PSPACE-úplného problému by znamenalo, že máme jednoduché řešení všech ostatních problémů v PSPACE, protože všechny PSPACE problémy lze redukovat na PSPACE-úplný problém.[11]

Příkladem PSPACE-úplného problému je problém kvantifikovaného Booleovského vzorce (obvykle zkráceně na QBF nebo TQBF; T znamená „pravdivý“).[11]

  1. Sipser 1997, Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
  2. Sipser 2006, Chapter 8: Space Complexity.
  3. Papadimitriou 1993, Chapter 19: Polynomial space, pp. 455–490.
  4. Arora a Barak 2009, s. 81.
  5. Arora a Barak 2009, s. 85.
  6. Arora a Barak 2009, s. 86.
  7. Arora a Barak 2009, s. 100.
  8. QIP-PSPACE.
  9. Aaronson 2005.
  10. Watrous a Aaronson 2009.
  11. a b Arora a Barak 2009, s. 83.

V tomto článku byl použit překlad textu z článku PSPACE na anglické Wikipedii.

Literatura

[editovat | editovat zdroj]

Externí odkazy

[editovat | editovat zdroj]