Problemy trudne obliczeniowo Zadania

Czȩść trzecia

Damian Niwiński

Maj 2001

Zadania punktowane

1. (1 pt.) Zakładaj _{}ac NP–zupełność problemu 3–CNF SAT , udowodnić, że dla każdej ustalonej liczby k ≥ 3, nast_{}epuj _{}acy problem jest NP–zupełny

• Dany graf G. Pytanie: czy G jest k–kolorowalny?

2. (3 pt.) Udowodnić, że dla k = 3 problem z zadania 1 jest NP–zupełny nawet, kiedy ograniczymy si_{}e do grafów planarnych (pytanie, czy dany graf jest planarny można rozstrzygn _{}ać w czasie wielomianowym dzi_{}eki twierdzeniu Kuratowskiego). Co można powiedzieć o analogicznym problemie dla k = 4 ?

3. (1 pt.) Wykazać, że problem spełnialności dla formuł w postaci 2–CNF (koniunkcje alternatyw dwóch literałów) jest rozstrzygalny w czasie wielomianowym.

4. (3 pt.) Zbadać złożoność problemu spełnialności dla formuł zdaniowych, w których każda zmienna wyst_{}epuje co najwyżej dwa razy (poza tym nie zakładamy specjalnej postaci formuły).

5. (1 pt.) Przypomnijmy, że NC^{1} jest klas _{}a j_{}ezyków, jakie mog _{}a być rozpoznawane przez ci _{}agi obwodów logicznych C_{n} o rozmiarze wielomianowym wzgl_{}edem n i gł_{}ebokości O(log n). Udowodnić, że j_{}ezyk PARITY jest w NC^{1}. Oszacować złożoność funkcji, która dla danego 1^{n} znajduje obwód C_{n} dla j_{}ezyka PARITY .

6. (2 pt.) Udowodnić, że każdy j_{}ezyk regularny jest w NC^{1}. Podać przykład j_{}ezyka nieregularnego w NC^{1}.