Editace stránky Složitost II

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Varování: Nejste přihlášen(a). Pokud uložíte jakoukoli editaci, bude vaše IP adresa zveřejněna v historii této stránky. Pokud se přihlásíte nebo si vytvoříte účet, budou vaše editace připsány vašemu uživatelskému jménu a získáte i další výhody.

Editace může být zrušena. Zkontrolujte a pak potvrďte změny zobrazené níže.
Aktuální verze Váš text
Řádka 186: Řádka 186:
  
 
Stroj M' udělá nejvýše <math>T'(n) \le k \sum_{i=1}^{log_2(T(n))+1}(m 2^{i-1} \frac{T(n)}{2^{i-1}}) \le 2mkT(n)\log_2T(n)</math>. A díky větě o lineárním zrychlení existuje DTS simulujicí M' v čase <math>T(n)\log_2T(n)</math>.
 
Stroj M' udělá nejvýše <math>T'(n) \le k \sum_{i=1}^{log_2(T(n))+1}(m 2^{i-1} \frac{T(n)}{2^{i-1}}) \le 2mkT(n)\log_2T(n)</math>. A díky větě o lineárním zrychlení existuje DTS simulujicí M' v čase <math>T(n)\log_2T(n)</math>.
 +
 +
 +
'''Důsledek''': Nechť je L přijímán k-páskovým NTS M s časovou složitostí T(n). Potom existuje 2-páskový NTS M' s časovou složitostí <math>T(n) * log_2(T(n))</math> přijímajicí L.
  
 
Poznámka: Důkaz lze upravit i pro NTS.
 
Poznámka: Důkaz lze upravit i pro NTS.
Řádka 214: Řádka 217:
 
<math>\Rightarrow</math>: zřejmá. Stroj pro čas. konst. upravíme, aby v každém kroku zapsal 1 na výstup, nový stroj vyhovuje požadavkům vpravo, c = 1.
 
<math>\Rightarrow</math>: zřejmá. Stroj pro čas. konst. upravíme, aby v každém kroku zapsal 1 na výstup, nový stroj vyhovuje požadavkům vpravo, c = 1.
  
<math>\Leftarrow</math>: f je vyčíslená transducerem M, který nad vstupem délky n udělá g(n) kroků, <math>g(n) \leq c\cdot f(n)</math>.
+
<math>\Leftarrow</math>: f je vyčíslená transducerem M s časovou složitostí g(n), <math>g(n) \leq c\cdot f(n)</math>.
  
 
* g je časově konstruovatelná (existuje M)
 
* g je časově konstruovatelná (existuje M)
Řádka 337: Řádka 340:
 
* <math>M_4</math> přijme x, když <math>M_3</math> přijme.
 
* <math>M_4</math> přijme x, když <math>M_3</math> přijme.
  
Stačí, že si poradíme jen s <math>2^{S_2(f(n))}</math> dolary? <math>S_2(n) \geq n, f(n) \geq n</math>, tedy <math>2^{S_2(f(n))} \geq f(n) \geq i</math> = počet dolarů. Zkonstruovali jsme <math>M_4</math> přijímající <math>L_1</math> v prostoru <math>S_2(f(n))</math>, <math>L_1 \in NSPACE(S_2(f(n)))</math>.  
+
Stačí, že si poradíme jen s <math>2^{S_2(f(n))}</math> dolary? <math>S_2(n) \geq n, f(n) \geq n</math>, tedy <math>2^{S_2(f(n))} \geq f(n) \geq i</math> = počet dolarů. Zkonstruovali jsme <math>M_4</math> přijímající <math>L_1</math> v čase <math>S_2(f(n))</math>, <math>L_1 \in NSPACE(S_2(f(n)))</math>.  
  
 
'''Poznámka''': Platí pro DSPACE, NTIME i DTIME.
 
'''Poznámka''': Platí pro DSPACE, NTIME i DTIME.
Řádka 366: Řádka 369:
 
== Kuriozity ==
 
== Kuriozity ==
 
=== Borodinova věta o mezerách ===
 
=== Borodinova věta o mezerách ===
Nechť <math>g(n) \geq n</math>, g je rekurzivní funkce. Potom existuje rekurzivní rostoucí funkce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n))).
+
Nechť <math>g(n) \geq n</math>, g je rekurzivní funkce. Potom existuje rekurzivní fce S(n) taková, že DSPACE(S(n)) = DSPACE(g(S(n))).
  
 
'''Důkaz''':  
 
'''Důkaz''':  
Řádka 372: Řádka 375:
 
Nechť <math>M_1, M_2, ...</math> je očíslování všech DTS. <math>S_i(n)</math> je max. počet použitých buněk při práci i-tého stroje nad vstupem délky n (pokud zastaví). Pro dané i, n, m lze ověřit, zda <math>S_i(n)\leq m</math>.
 
Nechť <math>M_1, M_2, ...</math> je očíslování všech DTS. <math>S_i(n)</math> je max. počet použitých buněk při práci i-tého stroje nad vstupem délky n (pokud zastaví). Pro dané i, n, m lze ověřit, zda <math>S_i(n)\leq m</math>.
  
Zkonstruujme S(n) takovou, že pro každý (k-tý) stroj platí jedna z podmínek:
+
Zkonstruujme S(n) takovou, že pro každý (k-tý) stroj platí aspoň jedna z podmínek:
  
 
* <math>S_k(n) < S(n)</math> skoro vždy
 
* <math>S_k(n) < S(n)</math> skoro vždy
* <math>g(S(n)) \leq S_k(n)</math> nekonečně často
+
* <math>S(g(n)) \leq S_k(n)</math> nekonečně často
  
Pro takové S neexistuje stroj <math>M_k</math> takový, aby pro všechna n: <math>S(n) < S_k(n) \leq g(S(n))</math>. Tedy každý DTS buď leží "před S(n)" (v obou třídách, "skoro vždy" ošetříme automatem, jazyk se zachová), nebo "za g(S(n))" (v ani jedné ze tříd, "nekonečně často" nelze ošetřit, nelze nacpat před g(S(n)) ).
+
Pro takové S neexistuje stroj <math>M_k</math> takový, aby pro všechna n: <math>S(n) < S_k(n) \leq S(g(n))</math>. Tedy každý DTS buď leží "před S(n)" (v obou třídách), nebo "za S(g(n))" (v ani jedné ze tříd).
  
 
Zkonstruujme funkci S. Jak spočteme S(n) pro dané n?  
 
Zkonstruujme funkci S. Jak spočteme S(n) pro dané n?  
  
Položme j=1, spočítejme g(j). Zkontrolujme pro <math>i \in (1 ... n)</math>, zda pro nějaký stroj <math>M_i</math>: <math>j < S_i(n) \leq g(j)</math>. Pokud takový stroj neexistuje (všechny stroje pracují v prostoru mimo interval), položme S(n) = j. Jinak položme <math>j = S_i(n)</math> a proces zopakujme. Spodní hranice j se posouvá nahoru, po nejvýše n iteracích budou všechny stroje <math>M_1 ... M_n</math> pod j, nebo nad g(j). Co dělají ostatní stroje nás nezajímá.
+
TODO.
 
+
Podívejme se na stejnou věc z hlediska libovolného stroje <math>M_k</math>. Pro i>k je <math>S_i(n)</math> vždy mimo "kritický interval". Pokud není skoro vždy pod ním, musí být nekonečně často nad ním.
+
  
 
'''Poznámka''': Platí pro NSPACE, NTIME i DTIME.
 
'''Poznámka''': Platí pro NSPACE, NTIME i DTIME.
Řádka 535: Řádka 536:
  
 
Existuje několik různých definic polynomiální hierarchie; kromě výše uvedené pracující s kvantifikátory se často (i na naší přednášce) používá definice pomocí strojů s orákuly řešícími nižší úroveň hierarchie. V orákulu jsou vlastně zavřeny všechny kvantifikátory kromě prvního, ten je počítán "vnějším" strojem.
 
Existuje několik různých definic polynomiální hierarchie; kromě výše uvedené pracující s kvantifikátory se často (i na naší přednášce) používá definice pomocí strojů s orákuly řešícími nižší úroveň hierarchie. V orákulu jsou vlastně zavřeny všechny kvantifikátory kromě prvního, ten je počítán "vnějším" strojem.
 
=== Věta o vztahu PH a PSPACE ===
 
 
<math>PH \subseteq PSPACE</math>.
 
 
Důkaz:
 
 
Chceme dokázat, že <math>\forall k: \Sigma_k  \subseteq PSPACE</math>. Indukcí:
 
 
1) <math>\Sigma_0 = P  \subseteq PSPACE</math>.
 
 
2) Nechť <math>\Sigma_k \subseteq PSPACE</math>. Pak <math>\Sigma_{k+1} = NP(\Sigma_k) \subseteq NP(PSPACE) \subseteq PSPACE(PSPACE)</math>. První inkluze plyne z indukčního předpokladu, druhá z toho, že orákulový NTS v poly čase se vejde do poly prostoru.
 
 
Teď stačí ukázat, že PSPACE(PSPACE) = PSPACE. Buď A z PSPACE(PSPACE). Tedy existuje B z PSPACE a DTS M, A = L(M, B). Existuje taky DTS M' pro B, pracující v poly prostoru.
 
 
Udělejme DTS M2, pracující v poly prostoru, přijímající A. M2 simuluje M a ve stavu DOTAZ spustí M' nad dotazovací páskou. Obě "úrovně" simulace se vejdou do poly prostoru, tedy A je z PSPACE.
 
  
 
== Převoditelnost a úplnost ==
 
== Převoditelnost a úplnost ==
Řádka 583: Řádka 568:
 
Jazyk kódů prázdných bezkontextových gramatik.
 
Jazyk kódů prázdných bezkontextových gramatik.
  
=== Věta (QBF je PSPACE-úplný) ===
+
=== Příklad PSPACE-úplného problému ===
  
QBF (bez volných proměnných) je PSPACE-úplný.
+
QBF-problém
 +
* vstup: QBF bez volných proměných.
 +
* výstup: true/false.
 +
 
 +
 
 +
QBF - kvantifikované boolovské formule. V anglicke terminologii se tomu taky rika (bez tech volnych promennych) TQBF.
 +
 
 +
 
 +
'''Lemma:''' QBF &isin; PSPACE.
  
 
''Důkaz:''
 
''Důkaz:''
  
1) Ukažme, že QBF &isin; PSPACE. Procedura '''eval''' rekurzivně počítá QBF.
+
procedura '''eval''' rekurzivně počítá QBF.
  
 
* QBF je konstanta <=> '''eval''' vrátí konstantu
 
* QBF je konstanta <=> '''eval''' vrátí konstantu
Řádka 597: Řádka 590:
 
:(&forall; x) E(x) vrací '''eval''' hodnotu výrazu E(0) &and; E(1) //domena pro x je len {true, false}, tj. {0,1}
 
:(&forall; x) E(x) vrací '''eval''' hodnotu výrazu E(0) &and; E(1) //domena pro x je len {true, false}, tj. {0,1}
  
V QBF je nejvýš ''n'' operátorů a kvantifikátorů, hloubka rekurze '''eval''' je tedy nejvýš ''n''. Pracovní páska DTS slouží jako zásobník aktivačních záznamů procedury '''eval''', každý takový záznam je jen polynomiálně velký v ''n''. Celkový použitý prostor je polynomiální.
 
 
2) Ukažme, že QBF je "PSPACE-těžký", tedy že &forall; L &isin; PSPACE : L lze polynomiálně převést na QBF.
 
 
L je z PSPACE, tedy existuje DTS M přijímající L v poly prostoru S(n). Pro každé slovo w chceme umět zkonstruovat QBF f, která bude TRUE, právě když w je v L. Nechť c1, c2 jsou dvě konfigurace M, t přirozené číslo. Nechť QBF <math>\phi_{c1,c2,t}</math> má hodnotu TRUE, když M se může dostat z c1 do c2 po nejvýše t krocích. Konkatenace konfigurací c1, c2 je zároveň ohodnocení proměnných. Pak našim cílem je <math>f = \phi_{c_{start},c_{accept},T}</math>, <math>c_{start}</math> je počáteční konfigurace, c_{accept} koncová a T je maximální počet kroků, který M může potřebovat. Víme, že <math>T = d^n</math> pro konstantu d (tj. počet konfigurací v prostoru S(n) je "exponenciální").
 
  
Naše QBF f má hodnotu TRUE, právě když w patří do L. Při znalosti M a slova w, potřebujeme zkonstruovat f v poly čase.
+
V QBF je nejvýš ''n'' operátorů a kvantifikátorů, hloubka rekurze '''eval''' je tedy nejvýš ''n''.
  
* t = 1, <math>\phi_{c1,c2,t}</math> - formule je jasná, buď DTS se po 1 kroku dostane do c2, nebo nedostane.
+
Pracovní páska DTS slouží jako zásobník aktivačních záznamů procedury '''eval''', a každý takový záznam je jen polynomiálně velký v ''n''.  
* t > 1, <math>\phi_{c1,c2,t}</math> - formuli rekurzivně složíme ze dvou, a to: <math>\exists m_1(\phi_{c1,m_1,\lceil t/2 \rceil} \wedge \phi_{m_1,c2,\lceil t/2 \rceil})</math>
+
  
Jelikož T je exponenciálně velké, naše formule f bude exponenciálně dlouhá. Všimněte si, že jsme vůbec nepoužili všeobecný kvantifikátor. Zkusme to definovat jinak.
+
Celkový použitý prostor je polynomiální.
  
* t > 1, <math>\phi_{c1,c2,t}</math> jako <math>\exists m_1 \forall c3 \forall c4 ((c3,c4)=(c1,m_1) \vee (c3,c4)=(m_1,c2)) \Rightarrow \phi_{c3,c4,\lceil t/2 \rceil})</math>
+
To dokazuje ze QBF &isin; PSPACE. Zel tu ale neni dukaz toho, ze kazdy Q &isin; PSPACE je na QBF v pol. case prevoditelny! (Coz by spolu znamenalo, ze QBF je PSAPCE-uplny). Je ale v knihe C. H. Papadimitriou: "Computational Complexity", na stranach 456 - 458, cize trochu drsne, asi to nikdo nikdy na matfyze nebude chciet.
  
Výraz před konjunkcí lze přepsat do CNF velikosti c*S(n). Máme však pouze jedno "rekurzivní volání". Velikost celé f tedy bude cca <math>S(n)^2</math>. Stejnou velikost má i prostor a čas naší konstrukce f (půlením T se z exp. času vrátíme do poly času).
+
'''JM''' ta konstrukce je velmi podobna dukazu Savicovy vety jen misto procedury TEST mame FORMULI_TEST. Neni tomu nahodou, TQBF je uplny problem nejen pro PSPACE ale i pro NPSPACE (se stejnou konstrukci) a tedy se takhle da taky dokazat ze NPSPACE = PSPACE. A taky je to celkem dobre vysvetleny na [https://en.wikipedia.org/wiki/True_quantified_Boolean_formula anglicky wiki]
  
===Poznámka===
 
  
V důkazu výše vůbec není zřejmé, jak se staví formule. Popisuje se rekurzivní vlastnost, avšak kvantifikují se konfigurace. QBF musí obsahovat booleovské proměnné.
+
'''Lemma:''' &forall; L &isin; PSPACE : L lze polynomiálně převést na QBF
  
'''Jak by šel důkaz výše interpretovat:'''  Navrhuji následující konstrukci QBF. Pro reprezentaci konfigurace potřebujeme cca S(n) znaků. Konfiguraci tedy můžeme reprezentovat pomocí cca S(n) booleovských proměnných. Kvantifikaci konfigurace <math>\exists C</math> přepíšeme na kvantifikaci bool. proměnných <math>\exists c_1 \exists c_2 ... \exists c_{S(n)}</math>. Rovnost konfigurací přepíšeme na rovnost prvních, druhých ... bool. proměnných: <math>(C = D)  --->  (c_1=d_1 \wedge c_2=d_2 \wedge ... \wedge c_{S(n)}=d_{S(n)})</math>, kde rovnost bool. proměnných přepíšeme takto: <math>(c=d) ---> (c \wedge d) \vee (\neg c \wedge \neg d)</math>. Pokud je jedna konfigurace konstantní, lze to ještě víc zjednodušit.
+
Idea: Jestliže L &isin; PSPACE, potom existuje DTS M, který rozhoduje L v nějakém polynomiálním prostoru S(n).
 +
Důkaz se provede tak, že ukážeme jak zkonstruovat QBF &phi;, takovou, že &phi; = true '''iff''' M vrací 1.
  
Jakmile se dostaneme na nejnižší úroveň (t=1), máme dvě konfigurace C,D (tedy S(n)+S(n) proměmnných) a stavíme QBF pravdivou právě tehdy, když lze z C přejít do D jedním krokem. Do dané QBF musíme zakódovat celou přechodovou funkci stroje M. Když přechodová funkce má K "řádků", QBF bude mít tvar <math>F_1 \vee F_2 \vee ... \vee F_K</math>, kde <math>F_i</math> říká, že konfigurace C splňuje levou stranu i-tého přechodu (displej, stav, ...) a konfigurace D splňuje pravou stranu i-tého přechodu (nový displej, posuny hlav ...).
+
Jak se to udělá je popsáno na 1 stránce v knize Arora, Barak: ''Computational Complexity: A Modern Approach''.
  
Délka celé QBF má být polynomiální, stejně tak čas její konstrukce (z definice převoditelnosti). Rekurzivní algoritmus se zanoří až S(n)-krát, na každé úrovni kvantifikuje 3 nové konfigurace = 3*S(n) nových bool. proměnných. Délka této části je kvadratická. Na nejnižší úrovni (t=1) se "přilepí" QBF o velikosti přechodové funkce M.
 
  
Zde nastává problém, když velikost M není omezená polynomem daného vstupu (stejný problém např. u Kachlíkování, kdy se vyrábí víc kachlíků, než je polynom vstupu). Fígl je ten, že polynomiální převoditelnost je definovaná mezi dvěma jazyky, nikoli mezi třídou a jazykem. Celý postup výše nepopisuje algoritmus převodu DTS na QBF, ale jen schéma spousty různých algoritmů, každý z nich převádí slovo na QBF pro jeden konkrétní DTS v poly-čase. Krátkých vstupů (jejichž polynom nepřekročí velikost stroje) je jen konečně mnoho a můžeme pro ně vyrobit konečný automat, který pro dané vstupy vrátí "konstantní True QBF", např. <math>\forall x (x \vee \neg x) </math> (nebo konstantní false QBF, pokud dané krátké slovo automat nepřijímá).
+
Poznámka: Pokud CNF doplním pouze existenčními kvantifikátory, dostanu QBF kterou když vyřeším, mám i odpověď na SAT (ale máme jen že je NP-těžký, jeho NP-úplnost nevíme).

Kliknutím na Save page

  • Potvrzujete, že vložené změny jsou vaším dílem, nebo jste oprávněni je zveřejnit a licencovat podle pravidel této stránky.
  • Potvrzujete, že smluvní podmínky níže uvedených licencí znáte a chápete, nebo se s nimi v nejbližší době seznámite.
  • Souhlasíte se zveřejněním svých změn podle licence MatfyzKing copyright
  • Souhlasíte se zveřejněním svých změn podle licence Creative Commons BY-NC-SA 2.0
  • Souhlasíte se zveřejněním svých změn podle licence GNU GFDL

Nevkládejte cizí díla bez prokazatelného souhlasu autora nebo držitelů práv!

Storno | Pomoc při editování (otevře se v novém okně)

Šablony použité na této stránce: