Zložitostné triedy Flashcards
Aké funkcie sú “slušné”?
Páskovo, resp. časovo konštruovateľné
Ako zapisujeme binárne DTS M s jednou pracovnou páskou?
<M>, presný tvar na str. 5
</M>
Čo potrebujeme na vyjadrenie hierarchie priestoru?
Jazyk, ktorý sa s menšou pamäťou riešiť nedá a väčšia mu stačí
Konštantný multiplikatívny nárast pamäte výpočtovú silu TS …
nezvyšuje, dôkaz pomocou simulácie viacpáskového na 1 páske
Vyslov a dokáž vetu o pamäťovej hierarchii
Str. 6
Znenie: Nech log(n) ≤ S1(n) = o(S2(n)), kde S2(n) je páskovo konštruovateľná. Potom DSPACE(S1(n)) ⊂ DSPACE(S2(n))
Dôkaz str. 6
Aký je to prefixný kód TS M?
Reťazec tvaru 1*<M>. Je zrejmé, že existuje DTS, kt. rozhoduje či reťazec z 0 a 1 je alebo nie je prefixným kódom nejakého TS (aký? ako na to?)</M>
Prečo nám stačí vo vete o pamäťovej hierarchii dokázať, že L(M1) != L(M2)?
IDK, nájdi to
Vďaka čomu vieme, že hierarchia pamäťovej zložitosti je nekonečná?
S(n)=2^2^2^2…^2 a veta o pam. hierarchii (pozri str. 8)
Vyslov a dokáž vetu o časovej hierarchii
Nech n ≤ T1(n)=o(T2(n)/log T1(n)), kde T2(n) je čas. konštruovateľná. Potom DTIME(T1(n)) ⊂ DTIME(T2(n)). Dôkaz podobne ako pam. hierarchia, keď tak pozri str. 8
Ako sa mení zložitosť pri prechode od k-páskového TS na jednopáskový?
Pamäťová sa zachováva a časová narastie kvadraticky
Vyslov vetu o prechode z k-páskového TS na 2 pásky, a dokáž
Ku každému k-páskovému T(n)-časovo ohraničenému TS Tk ex. ekv. dvojpáskový O(Tk(n)log Tk(n)) časovo ohraničený TS T2.
Dokáž, prečo je stroj po prechode na 2 pásky tak časovo ohraničený, ako je povedané vo vete
str. 9-10
Čo vieme použiť na dolný odhad na priestor a na čas?
Čas - prechodová postupnosť
Priestor - prechodová matica
Aký aspoň priestor potrebujú neregulárne jazyky?
log log n
Čo je suprémum, infímum f?
limita najnižšej hornej, najvyššej dolnej hranice postupnosti f(n), f(n+1),…
Definuj prechodovú post. medzi i a i+1 políčkom
Majme jednopáskový TS, s jednosmerne nekonečnou čítacou prepisovacou hlavou zároveň, kt. najprv zmení stav a potom pohne hlavou.
fixovaný výpočet, nejaké i => postupnosť stavov, v ktorých stroj prechádza hranicu medzi i a i+1
Ako označujeme prechodovú postupnosť medzi i a i+1 políčkom?
pp(i)
Vyslov lemu o rovnakej prechodovej postupnosti a teda akceptovaní iného slova, dokáž ju
Nech w=w1w2…wn je akc. jednopáskovým TS T a nech prechodová post. pp(i) je rovnaká ako pp(j) (i<j). Potom T akc. aj slovo w1w2…wiw(j+1)…wn
Strana 11
Vyslov inú podobu lemy o rovnakých pp
v=a1a2…an, u=b1b2…bm akc. 1páskovým TS T a pp medzi ai, ai+1 je rovnaká ako bj,bj+1. Potom T akc. aj slovo a1a2…aibj+1…bm, resp. b1b2…bjai+1…an
Ak T je T(n) časovo ohraničený, potom súčet dĺžok pp je najviac … (a dokáž prečo)
T(n), lebo spraví dokopy max T(n) krokov
Dokáž vetu 3.8 na str. 12 (wcw^R) (dolný odhad na čas)
str. 12
Pre TS s jednou vstupnou a jednou pamäťovou páskou je stav pamäte daný čím?
Obsahom pamäťovej pásky, polohou hlavy na pamäťovej páske, stavom konečnostavovej riadiacej jednotky
Ak je L(n) pásková zložitosť TS, tak počet rôznych stavov pamäte je … (horný odhad)
L(n)st^L(n) kde t je mohutnosť páskovej abecedy, s počet stavov
Čo je to prechodová matica?
str 14
Vyslov a dokáž vetu o rovnakej prechodovej matici pre 2 slová
str 14
Vyslov a dokáž vetu 3.10 o dolnom odhade na pamäť
str 15
Ako vieme jednoducho simulovať NTS na DTS?
Prehľadávanie stromu výpočtu do šírky, na jednu pásku ukladáme konf. NTS v kt. môže byť v čase i, na druhú generujeme dosiahnuteľné v čase i+1
Aká je zložitosť jednoduchej simulácie ak zložitosť NTS je T(n)≥n a S(n)≥log n? Aj dokáž
čas - O(T(n)S(n)d^T(n)) kde d je maximum počtu vetvení NTS
priestor - O(S(n)d^T(n))
teda exponenciálna
dôkaz na 16
Vyslov a dokáž Savitchovu vetu
Nech S(n)≥log(n) je páskovo konštruovateľná, potom NSPACE(S(n))⊆DPSACE(S^2(n))
dôkaz 17
Aký je vzťah DTIME, NTIME, DSPACE? veta 3.12
DTIME(T(n)) ⊆ NTIME (T(n)) ⊆ DSPACE(T(n)), prvá inklúzia jasná, druhá na str. 18
Aký je vzťah DSPACE, NSPACE a DTIME? Dokáž (veta 3.13)
DSPACE(S(n)) ⊆ NSPACE(S(n)) ⊆ zjednotenie c DTIME(c^(logn+S(n))) pre každú páskovo konštruovateľnú S(n) str 18 dole
Koľko rôznych konfigurácii môže nadobudnúť NTS s pam. zl. S(n), q stavmi, t symbolmi a k páskami?
(n+2)q[(S(n)+1)t^S(n)]^k, čo je menej ako d^(log(n)+S(n)) pre vhodnú konšt. d
Dokáž, že DLOG⊆NLOG⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP⊆NEXP
str 19, NSPACE(logn) ⊆ P vyplýva z vety 3.13, NP ⊆ PSPACE je dôsledkom vety 3.12, PSPACE = NPSPACE je dôsledkom Savitchovej vety a NPSPACE ⊆ EXP vyplýva z z vety 3.13.
Dokáž: Ak NSPACE(n^4) ⊆ NSPACE(n^3), potom NSPACE(n^20) ⊆ NSPACE(n^15).
str. 19
Vyslov Translačnú lemu a ideu dôkazu
Nech S1(n), S2(n) a f(n) sú páskovo konštruovateľné funkcie, S2(n) ≥ n, f(n) ≥ n. Potom platí:
ak NSPACE(S1(n)) ⊆ NSPACE(S2(n)) potom NSPACE(S1(f(n))) ⊆ NSPACE(S2(f(n)))
idea dôkazu: ako tvrdenie 3.1
Dokáž: NSPACE(n3) je vlastná podmnožina NSPACE(n4).
str. 20
Dokáž (predpoklad vety o medzere): Existuje rekurzívna funkcia S(n) ≥ n, pre ktorú: DSPACE(S(n)) = DSPACE(2^S(n)).
str. 21
Vyslov a dokáž vetu o medzere
Pre každú rekurzívnu funkciu g(n) ≥ n existuje rekurzívna funkcia S(n) ≥ n taká, že platí:
DSPACE(S(n)) = DSPACE(g(S(n))).
Vyslov a dokáž speedup theorem
Pre každú rekurzívnu funkciu f(n) ≥ n^2 existuje rekurzívny jazyk L taký, že pre ľubovoľný T-stroj M akceptujúci L v čase T(n) existuje T-stroj M′ tiež akceptujúci L, v čase T′(n) tak, že f(T′(n)) ≤ T(n) pre skoro všetky n.
Vyslov a dokáž Immerman-Szelepcsényiho vetu
Nech funkcia f(n) je konštruovateľná, pričom f(n) ≥ logn. Potom trieda NSPACE(f(n)) je uzavretá na komplement.
Dôkaz str. 22
