-
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.