SLOŽITOST

Question 1

Jazyky a problémy, vztah rekurzivních a částečně rekurzivních jazyků k jazykům Chomského hierarchie

Answer 1

Pojmy k vysvětlení:
Jazyk …
Jazyk přijímaný TS M - L(M) …
…příj, zamít, cykl
TS rozhoduje jazyk L když…
rozpoznává
TS - … + definice
Konfigurace …
Páska …, teor neomez, posun jak
varianty dle pásky

Problémy rozhodnutelné - rekurzivně enum
nerozhodnutelné - částečně rekurz

Chomsky hierarchie, popsat, příklady

Nerozhodnutelné problémy:
Acceptance TM
Halt TM
Empty TM
Equal TM

Question 2

Riceova věta, věta o rekurzi a jejich aplikace

Answer 2

Rice theorem
Co je to vlastnost jazyka
Co je to netriviální vlastnost
Nerozhodnutelnost
Důsledky

Úvod věty o rekurzi
Sebereference
Lemma
Důkaz
Věta o rekurzi
Důkaz
Využití

Question 3

Složitosti algoritmů a třídy složitosti, PTIME, NPTIME, NP-co, coNP

Answer 3

Motivace, teorie složitosti, definice
Asymptotická notace

Def DTIME NTIME

P, NP, př na HAMPATH

NP-úplné - Stephen Cook a Leonid Levin

SAT
Cook-Levinova věta - SAT je NP-co
Kdy je L NP-co?

Idea důkazu

Question 4

Další třídy složitosti SPACE, D, N, P, NP, Savitchova věta

Answer 4

• Prostorová složitost TS - dts/nts
• Pro odhad asymptotická notace
• TS pracuje s pamětí S(n) ..
• DSPACE, NSPACE
• Paměť mocnější než čas..
• Savitchova věta
• porovnání s časovou omezeností
• NSPACE f(n) Ul DSPACE f^2(n)
• Proč naivní důkaz nefunguje
• CanYield slovně, yieldability problem
• Formálně, algoritmus, why it works
• Co nám Savitch Věta říká?
• PSPACE, NPSPACE
• Vztahy:
  P UI PSPACE, NP UI NPSPACE
  P ui NP ui PSPACE = NPSPACE ui EXPTIME

Question 5

PSPACE-úplné problémy

Answer 5

PSPACE úplnost definice
Motivace - nejtěžší problémy v pspace, pokud bychom našli efektivní řešení pro pspace-co, našli bychom efektivní řešení pro všechny pspace problémy. proč ptime redukovatelnost? redukce musí být easy relativně k řešení problémů, tudíž omezená redukce časově (je větší omezení než paměťově)
TQBF popis, tqbf je pspace hard
Winning strategy
Formula game je pspace-co
GG
GG je pspace-co

Question 6

Třídy složitosti L a NL

Answer 6

logspace a nondeterministic logspace
úprava ts
kdy je jazyk nl-úplný
PATH € NL

NL-úplnost
A <=log B
Log space transducer

NL=coNL
coPATH € NL

L < NL = coNL < P < PSPACE

Question 7

Alternující TS a přísluš. třídy slož

Answer 7

Co to je
Definice
-ATIME
-ASPACE
-AP, APSPACE, AL
TAUT

Question 8

Paralelní algoritmy, výpoč. obvody a třídy AC, NC

Answer 8

PRAM, alt. BOOL obvody
Výhody, nevýhody
Komplex výpočtu - velikost, hloubka
Definice rodiny bool obvodů
velikostní složitost, hloubková složitost
NC
AC

Question 9

P-úplnost

Answer 9

Motivace, úvod
Def jazyk je p-co
Věta A <=log B a B € NC, pak A € NC
Circuit-Value
proč jsou p-úplné problémy sekvenční

další: linear programming s konstantnimi variables
membership in context free gramatice

Question 10

Polynomická hierarchie

Answer 10

úvod, motivace
pspace úplnost
np-úplnost
existuje PH-úplný jazyk? NE

Question 11

Pravděpodobnostní algoritmy a přísl. třídy slož

Answer 11

Popis pravděp alg, chybovost epsilon, motivace
Definice P(větve b)
P(M přijímá w) = suma přijímacích větví / P(M zamítá)…
Třídy:
BPP (bounded e), Amplifikační lemma, coBPP (=)
RP (randomized ptime), coRP
ZPP (zero error prob ptime) yes/no/dunno

P<RP<NP
RP<BPP
coRP<BPP

Testování prvočíselnosti
- náhodné číslo, rozklad, pár testů, pokud podmínky platí, přijímá, pokud ne, nevíme jistě