1. (5b) Existuje jazyk, ktory je rozhodovany v case T(n) = Theta(2^n) na 1-paskovom turingovom stroji a v case O(n^2) na viacpaskovom.
2. (10b) Aku priestorovu a casovu zlozitost bude mat turingov stroj ekvivalentny MRAMu, ak jeho priestorova zlozitost:
   a. O(n^2 log(n)) pri jednotkovej cene
   b. stvrta odmocnina z (n^7) pri logaritmickej cene
3. (5b) Vysvetlite pojem "prechodova postupnost" a popiste jej vyuzitie pri dolnych odhadoch na cas.
4. (10b) Dokazte alebo vyvratte: DTIME(sqrt(n^5)) = DTIME(c*sqrt(n^5)); c je z (0;1)
5. (10b) Na vstupe je dana Boolovska formula BF(x1;...;xn) a prirodzene cislo k. Vystupom je 1, ak je splnenych prave k elementarnych disjunkcii, 0 inak. Skonstruujte prislusny TS.
6. (12b) Definujte silno NP-tazky problem a pseudopolynomiaalny algoritmus. Dokazte, ze ak P<>NP, potom pre silno NP-tazky problem neexistuje pseudopolynomialny algoritmus.
7. (8b) Definujte aproximacny algoritmus, relativnu chybu, definujte PTAS, FPTAS.