Złożoność obliczeniowa | Informatyka MIMUW

Konstruowalność pamięciowa. Skonstruować maszynę Turinga off-line, która dla wejścia $w$ o długości $n$ zużywa dokładnie $f(n)$ komórek pamięci roboczej, gdzie

$f(n)=2n,n^{2},n^{k},2^{n},\log n,\ldots$
Konstruowalność czasowa. Skonstruować maszynę Turinga, która dla wejścia $w$ o długości $n$ wykonuje dokładnie $f(n)$ kroków, gdzie $f(n)=2n,3n,n^{2},n^{k},2^{n},2^{{2^{n}}},\ldots$ .
Dowieść, że klasy $P$ , NP i PSPACE są zamknięte na operację *.
Problem domina. Instancja problemu domina obejmuje liczbę naturalną $M$ daną unarnie oraz skończony zbiór wzorców kostek domina, tzn. wektorów postaci (up, down, left, right ), gdzie up, down, left i right są binarnie zadanymi liczbami, które w tym kontekście nazywamy kolorami. (Liczba kolorów nie jest ograniczona, a więc zależy od danej instancji problemu.) Pytanie brzmi: czy kwadrat $M\times M$ można pokryć kostkami domina w ten sposób, że sąsiednie kostki stykają się bokami o tym samym kolorze, a na bokach kwadratu jest kolor 0 (“biały”). Zakładamy przy tym, że każdy wzorzec można wykorzystać dowolnie wiele razy, ale nie można go “obracać” (tzn. up jest zawsze górną krawędzią itd.).

Należy udowodnić, że problem domina jest NP-zupełny. Wskazówka : zastosować redukcję generyczną, tzn. wychodząc od dowolnej niedeterministycznej maszyny Turinga działającej w czasie wielomianowym.
Udowodnić, że następujący problem dokładnego pokrycia (ang. exact cover) jest NP-zupełny. Dana rodzina podzbiorów $\{ 1,2,\ldots,n\}$ (liczby dane binarnie). Pytanie: czy istnieje podrodzina podzbiorów rozłącznych, które w sumie dają $\{ 1,2,\ldots,n\}$ .

Wskazówka : wykorzystać zadanie ??.
Udowodnić, że następujący problem plecakowy (ang. knapsack problem) jest NP-zupełny. Dane: liczby $n,m_{1},\ldots,m_{k}$ (binarnie). Pytanie: czy istnieje podzbiór zbioru $\{ m_{1},\ldots,m_{k}\}$ taki, że $m_{1}+\ldots+m_{k}=n$ .

Wskazówka : wykorzystać zadanie ??.
Dowieść, że złożenie dwóch funkcji obliczalnych w pamięci (przestrzeni) logarytmicznej jest funkcją obliczalną w pamięci logarytmicznej.
Dowieść, że każdy problem z klasy NP redukuje się do problemu 3-CNF SAT w pamięci logarytmicznej.