Problemy trudne obliczeniowo Zadania

Czȩść czwarta

Damian Niwiński

Sierpień 2001

Zadania punktowane

1. (1 pt.) Udowodnić, że klasy P i NP s _{}a zamkni_{}ete na operacj_{}e * (tzn. jeśli L ∈ C, to także L^{∗} ∈ C, dla C = P, NP).

2. (2 pt.) Udowodnić, że ograniczenie problemu 3–CNF SAT do formuł, w których każda klauzula ma dokładnie 3 różne literały, a ponadto każda zmienna wyst_{}epuje co najwyżej trzy razy, jest w klasie P.

Wskazówka. Rozważyć graf dwudzielny pomi_{}edzy klauzulami a literałami.

3. (1 pt.) Klauzul _{}a Horna nazywamy alternatyw_{}e literałów (tj. zmiennych lub ich negacji), w której co najwyżej jeden literał jest niezanegowan _{}a zmienn _{}a. Udowodnić, że problem CNF SAT ograniczony do koniunkcji klauzul Horna jest w klasie P.

4. (1 pt.) Określić złożoność nast_{}epuj _{}acego problemu (np. przez wykazanie zupełności w jakiejś klasie):

Dane s _{}a skończony automat niedeterministyczny A i skończony automat deterministyczny B. Pytanie: czy L(A) = L(B)?

Jak zmieni si_{}e odpowiedź jeśli założymy, że oba automaty s _{}a deterministyczne lub oba niedeterministyczne?

5. (1 pt.) Udowodnić, że j_{}ezyk {ww^{R} : w ∈ {0, 1}^{∗}} nie jest rozpoznawany przez żaden deterministyczny automat ze stosem.