Zložitostné triedy

Question 1

Aké funkcie sú “slušné”?

Answer 1

Páskovo, resp. časovo konštruovateľné

Question 2

Ako zapisujeme binárne DTS M s jednou pracovnou páskou?

Answer 2

<M>, presný tvar na str. 5
</M>

Question 3

Čo potrebujeme na vyjadrenie hierarchie priestoru?

Answer 3

Jazyk, ktorý sa s menšou pamäťou riešiť nedá a väčšia mu stačí

Question 4

Konštantný multiplikatívny nárast pamäte výpočtovú silu TS …

Answer 4

nezvyšuje, dôkaz pomocou simulácie viacpáskového na 1 páske

Question 5

Vyslov a dokáž vetu o pamäťovej hierarchii

Answer 5

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

Question 6

Aký je to prefixný kód TS M?

Answer 6

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>

Question 7

Prečo nám stačí vo vete o pamäťovej hierarchii dokázať, že L(M1) != L(M2)?

Answer 7

IDK, nájdi to

Question 8

Vďaka čomu vieme, že hierarchia pamäťovej zložitosti je nekonečná?

Answer 8

S(n)=2^2^2^2…^2 a veta o pam. hierarchii (pozri str. 8)

Question 9

Vyslov a dokáž vetu o časovej hierarchii

Answer 9

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

Question 10

Ako sa mení zložitosť pri prechode od k-páskového TS na jednopáskový?

Answer 10

Pamäťová sa zachováva a časová narastie kvadraticky

Question 11

Vyslov vetu o prechode z k-páskového TS na 2 pásky, a dokáž

Answer 11

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.

Question 12

Dokáž, prečo je stroj po prechode na 2 pásky tak časovo ohraničený, ako je povedané vo vete

Answer 12

str. 9-10

Question 13

Čo vieme použiť na dolný odhad na priestor a na čas?

Answer 13

Čas - prechodová postupnosť
Priestor - prechodová matica

Question 14

Aký aspoň priestor potrebujú neregulárne jazyky?

Answer 14

log log n

Question 15

Čo je suprémum, infímum f?

Answer 15

limita najnižšej hornej, najvyššej dolnej hranice postupnosti f(n), f(n+1),…

Question 16

Definuj prechodovú post. medzi i a i+1 políčkom

Answer 16

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

Question 17

Ako označujeme prechodovú postupnosť medzi i a i+1 políčkom?

Answer 17

pp(i)

Question 18

Vyslov lemu o rovnakej prechodovej postupnosti a teda akceptovaní iného slova, dokáž ju

Answer 18

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

Question 19

Vyslov inú podobu lemy o rovnakých pp

Answer 19

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

Question 20

Ak T je T(n) časovo ohraničený, potom súčet dĺžok pp je najviac … (a dokáž prečo)

Answer 20

T(n), lebo spraví dokopy max T(n) krokov

Question 21

Dokáž vetu 3.8 na str. 12 (wcw^R) (dolný odhad na čas)

Answer 21

str. 12

Question 22

Pre TS s jednou vstupnou a jednou pamäťovou páskou je stav pamäte daný čím?

Answer 22

Obsahom pamäťovej pásky, polohou hlavy na pamäťovej páske, stavom konečnostavovej riadiacej jednotky

Question 23

Ak je L(n) pásková zložitosť TS, tak počet rôznych stavov pamäte je … (horný odhad)

Answer 23

L(n)st^L(n) kde t je mohutnosť páskovej abecedy, s počet stavov

Question 24

Čo je to prechodová matica?

Answer 24

str 14

Question 25

Vyslov a dokáž vetu o rovnakej prechodovej matici pre 2 slová

Answer 25

str 14

Question 26

Vyslov a dokáž vetu 3.10 o dolnom odhade na pamäť

Answer 26

str 15

Question 27

Ako vieme jednoducho simulovať NTS na DTS?

Answer 27

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

Question 28

Aká je zložitosť jednoduchej simulácie ak zložitosť NTS je T(n)≥n a S(n)≥log n? Aj dokáž

Answer 28

č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

Question 29

Vyslov a dokáž Savitchovu vetu

Answer 29

Nech S(n)≥log(n) je páskovo konštruovateľná, potom NSPACE(S(n))⊆DPSACE(S^2(n)) dôkaz 17

Question 30

Aký je vzťah DTIME, NTIME, DSPACE? veta 3.12

Answer 30

DTIME(T(n)) ⊆ NTIME (T(n)) ⊆ DSPACE(T(n)), prvá inklúzia jasná, druhá na str. 18

Question 31

Aký je vzťah DSPACE, NSPACE a DTIME? Dokáž (veta 3.13)

Answer 31

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

Question 32

Koľko rôznych konfigurácii môže nadobudnúť NTS s pam. zl. S(n), q stavmi, t symbolmi a k páskami?

Answer 32

(n+2)q[(S(n)+1)t^S(n)]^k, čo je menej ako d^(log(n)+S(n)) pre vhodnú konšt. d

Question 33

Dokáž, že DLOG⊆NLOG⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP⊆NEXP

Answer 33

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.

Question 34

Dokáž: Ak NSPACE(n^4) ⊆ NSPACE(n^3), potom NSPACE(n^20) ⊆ NSPACE(n^15).

Answer 34

str. 19

Question 35

Vyslov Translačnú lemu a ideu dôkazu

Answer 35

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

Question 36

Dokáž: NSPACE(n3) je vlastná podmnožina NSPACE(n4).

Answer 36

str. 20

Question 37

Dokáž (predpoklad vety o medzere): Existuje rekurzívna funkcia S(n) ≥ n, pre ktorú: DSPACE(S(n)) = DSPACE(2^S(n)).

Answer 37

str. 21

Question 38

Vyslov a dokáž vetu o medzere

Answer 38

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))).

Question 39

Vyslov a dokáž speedup theorem

Answer 39

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.

Question 40

Vyslov a dokáž Immerman-Szelepcsényiho vetu

Answer 40

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