# Zápočet 27.1.2010

- Popiste TS pre jazyk $L=\{a^{i}b^{i}c^{i}; i \in N\}$
- Ukazke ze $sign(x)$ je PRF
- Za pomoci nektereho problemu z prednasky dokazte, ze Hamiltonovska cesta $HC(s,t)$ je NP-uplny problem
- Ukazte, ze pre hornovsku KNF existuje polynomialny algoritmus, ktory najde splnujuce ohodnotenie