Zadania

Na tej stronie znajdują się treści zadań, które pojawiły się na ćwiczeniach z Teorii Złożoności w semestrze letnim 2008.

Klasy P i NP

Przynależność do klas P i NP

  1. Pokazać, że następujące języki są w klasie P:
    a) MODEXP = {(a,b,c,p): a,b,c,p &isin N, ab &equiv c (mod p)}
    b) 2SAT = {&phi: &phi - spełnialna formuła 2CNF}
  2. Pokazać, że następujący język jest w klasie NP:
    ISO = {(G,H): G,H - nieskierowane grafy, izomorficzne}
  3. Czy następujący język jest w klasie P:
    HORNSAT = {&phi: &phi - spełnialna koniunkcja klauzul Horna (alternatyw, z których każda zawiera co najwyżej jeden niezanegowany literał)}?
  4. Pokazać, że klasa P jest zamknięta ze względu na operacje konkatenacji i gwiazdki.
  5. Pokazać, że klasa NP jest zamknięta ze względu na operacje przecięcia, sumy i konkatenacji.

Redukcje i problemy NP-zupełne

  1. Pokazać, że następujący problem jest NP-zupełny:
    TRIPLE_SAT = {&phi - formuła 3CNF, która ma co najmniej trzy wartościowania spełniające}
  2. Niech A,B będą nietrywialnymi językami nad alfabetem & (czyli A,B &ne &empty, &Sigma*). Pokazać, że:
    a) Jeśli B &isin P, to A &cap B &leP A.
    b) Jeśli język A &cup B jest NP-zupełny, A &isin NP, B &isin P, to A jest NP-zupełny.
  3. Niech ¬ L oznacza dopełnienie języka L. Pokazać, że L &leP ¬ L &hArr ¬ L &leP L.
  4. Niech L,L' będą językami takimi, że L &leP L'. Pokazać, że wtedy ¬ L &leP ¬ L'.
  5. Pokazać, że jeśli L1 &leP L2 oraz L2 &isin NP, to L1 &isin NP.
  6. Mówimy, że problem jest samoredukowalny, jeśli za pomocą wyroczni stwierdzającej, czy problem ma rozwiązanie, potrafimy w czasie wielomianowym znaleźć rozwiązanie tego problemu. Pokazać, że następujące problemy są samoredukowalne:
    a) 3SAT,
    b) 3-kolorowanie grafu,
    c) problem cyklu Hamiltona.

Klasa co-NP

  1. Pokazać, że jeśli NP &ne co-NP, to P &ne NP.
  2. Pokazać, że język L jest zupełny w klasie NP wtw. gdy język ¬ L jest zupełny w klasie co-NP.
  3. Niech TAUTOLOGY będzie językiem wszystkich formuł w rachunku zdań, które są tautologiami. Wykazać, że:
    a) TAUTOLOGY &isin co-NP.
    b) TAUTOLOGY jest co-NP-zupełne.
  4. Pokazać, że jeśli NP &cap co-NP zawiera problem NP-zupełny, to NP=co-NP.

Maszyny Turinga

  1. Pokazać, że dla danej maszyny Turinga M o k taśmach, działającej w czasie f(n), możemy utworzyć maszynę Turinga M' o jednej taśmie, działającą w czasie O(f(n)2) i rozpoznającą ten sam język.
  2. Pokazać, że maszyna Turinga z taśmą nieskończoną w jedną stronę jest równoważna maszynie Turinga z taśmą nieskończoną w obie strony.
  3. Pokazać, że kosztem zwiększenia alfabetu możemy zmniejszyć czas działania / pamięć maszyny Turinga o dowolną stałą multiplikatywną:
    - Jeśli L &isin TIME(f(n)), to &forall&epsilon > 0 L &isin TIME(&epsilon f(n)+n+2).
    - Jeśli L &isin SPACE(f(n)), to &forall&epsilon > 0 L &isin SPACE(&epsilon f(n)+2).
  4. Pokazać, że każdą maszynę Turinga o nieskończonej 2-wymiarowej taśmie można symulować za pomocą zwykłej maszyny Turinga (o kilku taśmach jednowymiarowych) z kwadratowym spadkiem efektywności (czyli maszynę działającą w czasie f(n) symulujemy w czasie O(f(n)2)).
  5. Pokazać, że maszyna Turinga z dodatkowymi operacjami INSERT (dodaje nową komórkę taśmy) i DELETE (usuwa bieżącą komórkę taśmy) może być symulowana przez zwykłą maszynę Turinga z kwadratowym spadkiem efektywności.
  6. Pokazać, że maszyna Turinga ze stałą pamięcią rozpoznaje tylko języki regularne.
  7. Pokazać, że maszyna Turinga, która nie może przesuwać głowicy w lewo, rozpoznaje tylko języki regularne.
  8. Pokazać, że dla niedeterministycznej maszyny Turinga o jednej taśmie działającej w czasie f(n) istnieje deterministyczna maszyna Turinga o jednej taśmie działająca w czasie 2O(f(n)) i rozpoznająca ten sam język.
  9. Jakie języki rozpoznaje maszyna Turinga o jednej taśmie, która nie może nadpisywać swojego wejścia (na dalszej części taśmy maszyna może pisać)?
  10. Maszyna Turinga write-once jest to maszyna Turinga o jednej taśmie, która może zmienić zawartość każdej komórki (włącznie z komórkami, na których zapisane jest wejście) dokładnie jeden raz. Jakie języki może rozpoznawać taka maszyna?
  11. Maszyna Turinga z operacją RESET jest to maszyna Turinga, która nie ma operacji przesunięcia głowicy o jedną pozycję w lewo, ale za to może przesunąć głowicę w lewo na początek taśmy (operacja RESET; maszyna ma taśmę nieskończoną w jedną stronę). Jakie języki może rozpoznawać taka maszyna?
  12. Pokazać, że maszyna Turinga o jednej taśmie działająca w czasie O(n) rozpoznaje tylko języki regularne.
  13. Niech PAL będzie zbiorem palindromów nad pewnym skończonym alfabetem. Pokazać, że:
    - Istnieje maszyna Turinga o jednej taśmie rozpoznająca język PAL w czasie O(n2).
    - Istnieje maszyna Turinga o dwóch taśmach rozpoznająca język PAL w czasie O(n).
    - Maszyna Turinga o jednej taśmie rozpoznająca język palindromów musi działać w czasie &Omega(n2).

Klasy L i NL

  1. Pokazać, że {0k1k: k &ge 0} &isin L.
  2. Pokazać, że PAL &isin L (PAL - zbiór palindromów).
  3. Pokazać, że język poprawnych wyrażeń nawiasowych (nawiasy jednego typu) jest w L.
  4. Czy język poprawnych wyrażeń nawiasowych w których występują dwa typy nawiasów jest w L?
  5. Niech PATH={(G,s,t): G jest grafem skierowanym, w którym istnieje ścieżka z s do t}. Pokazać, że PATH &isin NL.
  6. Pokazać, że problem PATH jest NL-zupełny.
  7. Pokazać, że jeśli A &leL B i B &isin L, to również A &isin L (przypomnienie: napis A &leL B oznacza, że język A można sprowadzić do B używając redukcji w pamięci lograytmicznej).
  8. Pokazać, że jeśli A &leL B i B &leL C, to również A &leL C.
  9. Pokazać, że {ww: w &isin {0,1}*} &isin L.
  10. Czy w pamięci logarytmicznej można policzyć
    a) sumę
    b) iloczyn
    dwóch liczb zapisanych binarnie?
  11. Pokazać, że język STRONGLY_CONNECTED = {G - graf skierowany, silnie spójny} jest zupełny w klasie NL.
  12. Czy istnienie redukcji w pamięci logarytmicznej z języka L1 do L2 implikuje istnienie redukcji wielomianowej z L1 do L2?
  13. Pokazać, że dane problemy można rozstrzygnąć w pamięci logarytmicznej:
    a) dla danego grafu nieskierowanego rozstrzygnąć, czy jest on acykliczny,
    b) dla danego grafu nieskierowanego rozstrzygnąć, czy jest on drzewem.
  14. Rozważmy język A={wk: k &isin N}, gdzie w1=0$1, w2=00$01$10$11 itd. (czyli wi jest konkatenacją wszystkich k-bitowych napisów uporządkowanych leksykograficznie i rozdzielonych symbolem $). Pokazać, że język A:
    a) nie jest regularny,
    b) jest rozstrzygalny w pamięci O(log log n).
  15. Pokazać, że DSPACE(o(log log n))=DSPACE(O(1)), czyli w pamięci o(log log n) można rozpoznawać tylko języki regularne.

Nierozstrzygalność

  1. Pokazać, że problem stopu (H={(M,x): maszyna Turinga M zatrzymuje się na słowie x}) jest nierozstrzygalny.
  2. Które z następujących języków są nierozstrzygalne?
    a) L = {M - maszyna Turinga, która zatrzymuje się dla każdych danych wejściowych},
    b) L = {M - maszyna Turinga, która zatrzymuje się dla pustego słowa wejściowego},
    c) L = {(M,x): obliczenie maszyny M na słowie x wykorzystuje wszystkie stany M},
    d) L = {(M,x,y): M(x)=y},
    e) L = {(M,x): M zatrzymuje się na słowie x po co najwyżej |x|2 krokach},
    f) L = {M: M zatrzymuje się na pewnym słowie wejściowym},
    g) L = {(M,&sigma): M wypisuje kiedykolwiek symbol &sigma},
    h) L = {(M1, M2): L(M1) = L(M2)},
    i) L = {(M1, M2): L(M1) &cup L(M2) = &Sigma*}.
  3. Czy istnieje maszyna Turinga M taka, że dla danego x stwierdzenie, czy M zatrzymuje się na x jest rozstrzygalne?
  4. Czy istnieje maszyna Turinga M taka, że dla danego x stwierdzenie, czy M akceptuje x jest nierozstrzygalne?
  5. Czy następujący problem jest rozstrzygalny: dla danego zestawu reguł przepisywania oraz słów x i y nad skończonym alfabetem &Sigma (np. ab &rarr ba, aa &rarr bab, bb &rarr a; x = ababba; y = aaaabbb) ustalić, czy za pomocą podanych reguł przepisywania można przekształcić słowo x na y?
  6. Czy następujący problem jest rozstrzygalny: dla danego zestawu reguł przepisywania oraz słowa x ustalić, czy za pomocą tych reguł możemy przekształcić x w dowolnie długi napis?
  7. Czy następujący problem jest rozstrzygalny: dla danego zestawu reguł przepisywania, w którym z lewej strony występują wyłącznie napisy długości 1, oraz słowa x ustalić, czy za pomocą tych reguł możemy przekształcić x w dowolnie długi napis?
  8. Pokazać, że dane języki są rozstrzygalne:
    a) EQ = {(A,B): A,B - deterministyczne automaty skończone takie, że L(A)=L(B)},
    b) ALL = {A - deterministyczny automat skończony taki, że L(A) = &Sigma*},
    c) L = {A - deterministyczny automat skończony, który nie akceptuje żadnego napisu zawierającego parzystą liczbę jedynek}
  9. Pokazać, że każdy język bezkontekstowy jest rozstrzygalny.
  10. Czy dane języki są rozstrzygalne:
    a) ALL = {G - gramatyka bezkontekstowa taka, że L(G) = &Sigma* },
    b) EQ = {(A,B): A,B - niedeterministyczne automaty ze stosem, dla których L(A)=L(B) },
    c) L = {(G,x): G - gramatyka bezkontekstowa taka, że L(G)={x} }?
  11. Problem Posta zdefiniowany jest następująco: Mamy dane n par słów (a1, b1), (a2, b2), ... (an, bn). Rozstrzygnąć, czy istnieje ciąg liczb i1, ... ,ik (dowolnej długości) taki, że ai1...aik = bi1...bik. Pokazać, że problem ten jest nierozstrzygalny.
  12. Pokazać, że problem Posta nad alfabetem jednoliterowym jest rozstrzygalny.
  13. Będziemy rozważać problem pokrycia płaszczyzny kostkami domina. Każda kostka jest kwadratem 1 × 1, a na każdym boku ma napisaną pewną liczbę naturalną. Mamy daną skończoną liczbę rodzajów kostek domina (za to każdą kostkę mamy w nieskończenie wielu egzemplarzach), z wyznaczoną kostką startową. Chcielibyśmy pokryć całą płaszczyznę takimi kostkami domina, zachowując warunki:
    - kostek domina nie można obracać (muszą być w takiej samej pozycji, co ich kostka wzorcowa),
    - domina stykające się bokami muszą mieć tę samą liczbę na sąsiadujących ze sobą bokach,
    - kostka startowa występuje na co najmniej jednej pozycji.
    Pokazać, że problem, czy danymi kostkami domina da się pokryć całą płaszczyznę, jest nierozstrzygalny.
  14. Co wiemy na temat zadania z poprzedniego punktu, jeśli:
    a) dopuścimy obracanie kostek o 180°,
    b) dopuścimy obracanie kostek względem osi pionowej (czyli zamienianie napisów na lewym i prawym boku),
    c) dopuścimy obracanie kostek względem ustalonej przekątnej (czyli np. jednoczesne zamienianie napisów lewy &harr górny i prawy &harr dolny)?
  15. Pokazać, że jeśli domina są oznaczane na rogach, zamiast na bokach (wszystkie 4 napisy stykające się w danym rogu muszą być taki same), to problem istnienia pokrycia całej płaszczyzny kostkami domina pozostaje nierozstrzygalny.
  16. Dla danego języka L język substring(L)={y | t. że xyz &isin L dla pewnych słów x,z}.
    a) Pokazać, że jeśli L jest rekurencyjnie przeliczalny, to substring(L) też.
    b) Czy jeśli L jest rozstrzygalny, to substring(L) też?

Alternacja

  1. Powiemy, że dwie formuły boolowskie &phi i &psi są równoważne, jeśli mają te same zmienne i dla każdego wartościowania v zachodzi &phi(v) = &psi(v). Formuła boolowska jest minimalna, jeśli nie istnieje któtsza formuła, która jest jej równoważna. Niech
    MIN_FORMULA = {&phi - minimalna formuła boolowska}. Pokazać, że MIN_FORMULA &isin AP.
  2. Pokazać, że:
    a) AL = P,
    b) AP = PSPACE,
    c) APSPACE = EXP.
  3. Rozważmy następującą grę dla dwóch graczy: Planszą jest graf skierowany i są na niej umieszczone dwa pionki: Adam i Ewa. Każda tura wygląda następująco: pierwszy gracz wskazuje dowolne puste pole, a następnie drugi gracz wybiera, który z dwóch pionków (Adama czy Ewę) przemieścić na to pole. Pierwszy gracz wygrywa, jeśli w pewnym momencie Adam zobaczy Ewę (czyli jest krawędź z pozycji Adama do pozycji Ewy). Drugi gracz wygrywa, jeśli w ciągu całej (nieskończonej) rozgrywki Adam nie zobaczy Ewy. Niech
    L = {(G,u,v): pierwszy gracz ma strategię wygrywającą na grafie G, jeśli Adam początkowo znajduje się na pozycji u, a Ewa na pozycji v}.
    Pokazać, że L &isin ASPACE(log n) oraz L &isin ATIME(log n).
  4. Alternująca maszyna Turinga one-read na każdej ścieżce obliczenia może tylko jeden raz wszytać symbol z taśmy wejściowej, w następujący sposób: dla wybranego symbolu &sigma &isin &Sigma oraz pozycji i sprawdza, czy na i-tej pozycji wejścia był zapisany symbol &sigma . Następnie maszyna kończy działanie w stanie akceptującym lub odrzucającym w zależności od tego, czy dany symbol się zgadzał.
    Pokazać, że alternującą maszynę Turinga, działającą w czasie T(n) &ge log n i pamięci S(n) &ge log n można symulować za pomocą maszyny one-read działającej w czasie O(T(n)) i pamięci O(S(n)).

Klasa PSPACE

  1. Pokazać, że jeśli f(n) &ge log n, to NSPACE(f(n)) &sube SPACE(f2(n)), czyli PSPACE = NPSPACE.
  2. Pokazać, że klasa PSPACE jest zamknięta ze względu na operacje:
    a) sumy,
    b) konkatenacji,
    c) gwiazdki.
  3. Pokazać, że jeśli problem jest PSPACE-trudny, to jest NP-trudny.
  4. Formuła &phi &isin QSAT, jeśli &phi jest postaci &existx1 &forallx2 &existx3 ... &psi(x1,...,xn), gdzie &psi jest formułą w postaci CNF. Pokazać, że QSAT &isin PSPACE.
    [QSAT jest PSPACE-zupełny, ale tego nie będziemy dowodzić]
  5. Gra GEOGRAPHY wygląda następująco: planszą jest graf skierowany, po którym gracze kolejno przesuwają jeden pionek. Ograniczenie jest następujące: każdej krawędzi można użyć co najwyżej jeden raz. Gracz, który nie może wykonać ruchu (wszystkie krawędzie wychodzące z aktualnego wierzchołka zostały już użyte), przegrywa. Niech GEOGRAPHY = {(G,v): pierwszy gracz ma strategię wygrywającą na G, jeśli pionek początkowo znajduje się w wierzchołku v}. Pokazać, że problem GEOGRAPHY jest PSPACE-zupełny.
  6. Niech EQ = {(R,S): R,S - równoważne wyrażenia regularne}. Pokazać, że EQ &isin PSPACE.
  7. Rozważmy następującą grę (punched card game): mamy talię (stos) kart, z których każda ma pewną liczbę otworów w dwóch kolumnach. Gracze na przemian pobierają jedną kartę ze stosu i układają ją na nowym stosie w jednej z dwóch pozycji: tak jak karta była ułożona na stosie początkowym lub obróconą o 180° . Pierwszy gracz wygrywa, jeśli w nowo powstałym stosie kart nie ma otworu przechodzącego przez wszystkie karty.
    Pokazać, że rozstrzygnięcie czy pierwszy gracz ma strategię wygrywającą jest PSPACE-zupełne.
  8. Gra "cat-and-mouse" jest rozgrywana przez dwóch graczy: "Kota" i "Myszę" na dowolnym nieskierowanym grafie. Gracze znajdują się początkowo w ustalonych wierzchołkach grafu. Gracze wykonują na przemian ruchy polegające na przesunięciu się na jeden z sąsiednich wierzchołków grafu. Jeden wyróżniony wierzchołek grafu to "dziura". Kot wygrywa, jeśli w pewnym momencie znajdzie się na tym samym polu, co mysz. Mysz wygrywa, jeśli uda jej się dotrzeć do dziury. Gra kończy się remisem, jeśli pewna sytuacja na planszy się powtórzy.
    Czy dla danego grafu, pozycji początkowych graczy oraz pozycji dziury potrafimy w czasie wielomianowym rozstrzygnąć, czy kot ma strategię wygrywającą? Zakładamy, że kot rusza się jako pierwszy.

Obwody logiczne

  1. Pokazać, że za pomocą obwodów logicznych rozmiaru O(n) można stwierdzić, czy dany ciąg binarny długości n ma parzystą liczbę jedynek.
  2. Niech addn: {0,1}2n &rarr {0,1}n+1 będzie funkcją obliczającą sumę dwóch n-bitowych liczb zapisanych binarnie. Pokazać, że możemy obliczać tę funkcję za pomocą obwodów logicznych rozmiaru O(n).
  3. Rodzina Ci obwodów logicznych jest jednostajna, jeśli istnieje maszyna Turinga M o złożoności pamięciowej O(log n), która dla danych wejściowych postaci 1n generuje Cn. Pokazać, że istnieją rodziny układów logicznych, które nie są jednostajne i rozwiązują problemy nierozstrzygalne.
  4. Pokazać, że:
    - obwody monotoniczne (bez negacji) mogą rozpoznawać tylko funkcje monotoniczne,
    - każda n-bitowa funkcja monotoniczna jest rozpoznawana przez pewien obwód logiczny o n wejściach.
  5. Pokazać, jak można zasymulować niedeterministyczny automat skończony przez ciąg obwodów logicznych (po jednym dla wejść każdej długości).

Randomizacja (klasy RP, BPP, PP, ZPP)

  1. Pokazać, że klasy RP i BPP są zamknięte ze względu na sumę i przecięcie.
  2. Pokazać, że:
    a) RP &sube NP,
    b) RP &sube BPP,
    c) co-BPP = BPP,
    d) PP &sube PSPACE,
    e) NP &sube PP,
    f) ZPP = RP &cap co-RP.
  3. Standardowo klasa PP zdefiniowana jest następująco: PP = {L &isin &Sigma*: &existmaszyna Turinga M x &isin L &rArr Pr[M(x)=1] > 1/2, x ¬in L &rArr Pr[M(x)=1] < 1/2}. Pokazać, że zmiana jednej z tych nierówności na nieostrą da nam tę samą klasę, czyli {L &isin &Sigma*: &existmaszyna Turinga M x &isin L &rArr Pr[M(x)=1] > 1/2, x ¬in L &rArr Pr[M(x)=1] &le 1/2}=PP. Co będzie, jeśli obie nierówności zamienimy na nieostre?
  4. Pokazać, że klasę ZPP można scharakteryzować następująco: jest to klasa problemów, dla których istnieje maszyna Turinga, która zawsze kończy działanie i zwraca poprawną odpowiedź, może działać dowolnie długo, ale jej oczekiwany czas działania jest wielomianowy.
  5. Pokazać, że jeśli NP &sube BPP, to RP=NP (wskazówka: Pokazać, że jeśli SAT &isin BPP, to SAT &isin RP).
  6. Pokazać, że jeśli P=PSPACE, to RP=BPP.

Dowody interaktywne (klasa IP)

  1. Pokazać, że klasa IP z weryfikatorem deterministycznym = NP.
  2. Niech GRAPH_NONISOMORPHISM = {(G,H): G,H - grafy nieizomorficzne}. Pokazać, że GRAPH_NONISOMORPHISM &isin IP.

Klasa PCP i aproksymacja

  1. Pokazać, że PCP(log n, 1) &sube NP.
  2. Pokazać, że z twierdzenia PCP wynika trudność aproksymacji problemu MAX 3SAT z pewnym stałym współczynnikiem:
    a) Problem MAX k-FUNCTION SAT zdefiniowany jest następująco: dane jest n zmiennych logicznych x1,...,xn oraz m funkcji zero-jedynkowych f1,...,fm, każda od k zmiennych. Znaleźć wartościowanie zmiennych x1,...,xn spełniające maksymalną możliwą liczbę funkcji.
    Udowodnić, że istnieje taka stała k i redukcja z problemu 3SAT do problemu MAX k-FUNCTION SAT, która przekształca formuły spełnialne w instancje problemu MAX k-FUNCTION SAT, w których można spełnić jednocześnie wszystkie funkcje, a formuły niespełnialne w takie instancje, w których każde wartościowanie spełnia mniej niż połowę funkcji.
    b) Pokazać, że istnieje redukcja problemu SAT do problemu MAX 3SAT, która przekształca formuły spełnialne w spełnialne, a niespełnialne na takie, dla których każde wartościowanie spełnia mniej niż pewną stałą część wszystkich klauzul (1-&epsilon dla pewnej stałej &epsilon).
  3. Podać algorytm 2-aproksymacyjny dla problemu minimalnego pokrycia wierzchołkowego (wskazówka: maksymalne skojarzenie).
  4. Pokazać, że problemu minimalnego pokrycia wierzchołkowego nie da się aproksymować z pewnym stałym współczynnikiem (wskazówka: MAX 3SAT, max. zbiór niezależny)
  5. Podać algorytm 2-aproksymacyjny dla metrycznego problemu komiwojażera (wskazówka: minimalne drzewo rozpinające).
  6. Pokazać, że problemu komiwojażera bez nierówności trójkąta nie można aproksymować z żadnym współczynnikiem (wskazówka: redukcja z problemu cyklu Hamiltona).
  7. Podać algorytm 2-aproksymacyjny dla problemu MAX CUT (podzielić wierzchołki grafu na 2 podzbiory tak, aby zmaksymalizować liczbę krawędzi między tymi podzbiorami) (wskazówka: zachłannie).
  8. Podać algorytm 2-aproksymacyjny dla problemu BIN PACKING (zapakować towary o różnych rozmiarach do jak najmniejszej liczby skrzyń o rozmiarze 1).