# Zápočet 10. 1. 2011

## Varianta A
- Napište TS, který rozpoznává následující jazyk: $1^{x+1}01^{x+2}$
- Ukažte, že $f(x):=x!$ je PRF
- Ukažte, že existuje $n$, pro které $W_n=\{k*n|k\in\mathbb{N}\}$. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.)
- Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný


## Varianta B
- Napište TS, který rozpoznává jazyk $1^{2^x}, x >= 0$. Stačil popis/postup.
- Ukažte, že $2^x, x>=0$ je PRF. (odvození)
- Ukažte, že existuje $n$, pro které $W_n=\{n^k | k \in\mathbb{N}\}$.
- Ukažte, že rozvrhování je NPC.