[NTIN090] Základy složitosti a vyč. - Záp 28.1.2010

Betlista: Matfyz(ák|ačka) level I; Příspěvky: 24; Registrován: 21. 11. 2007 14:59; Typ studia: Informatika Mgr.

[NTIN090] Základy složitosti a vyč. - Záp 28.1.2010

Příspěvek od Betlista » 28. 1. 2010 11:04

Verze E

1. Popište TS, který počítá funkci sčítání

2. Ukažte, že $x^y$ je PRF (můžete předpokládat, že sčítání a násobení PRF jsou)

3. Za pomoci některého problému, jehož těžkost jsme si ukazovali na přednášce, ukažte, že následující problém je NP-uplný:
Batoh
Instance: množina předmětů $U$ , s každým prvkem $u \in U$ je asociována jeho velikost $s(u) \in \mathbb{N}$ a cena $v(u) \in \mathbb{N}$ a jsou daná přirozená čísla B a K.
Otázka: Existuje množina $U' \subseteq U$ , pro kterou platí, že
$\sum_{u \in U'}s(u) \le B\quad a \quad \sum_{u \in U'}s(u) \ge K$ ?
Tj. lze do batohu velikosti B zabalit předměty s cenou alespoň K?

4. Definujeme-li problém DNF-SAT jako problém splnitelnosti formule v disjunktivně normální formě (DNF), jaká je složitost tohoto problému? Je to NP-úplný nebo patří do P?

PS: na začiatku sa niekto pýtal, či je možné používať materiály z prednášky (slajdy) a áno, je to povolené