Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 13

Ćwiczenie 1

W trakcie wykładu rozważaliśmy język

wykazując, że NP .

Uzasadnij, że także
P
Wskazówka
Rozwiązanie

Ćwiczenie 2

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie


Ćwiczenie 4

Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga akceptującej język:

Zmodyfikuj, ewentualnie, tę konstrukcję , aby udowodnić P .

Ćwiczenie 5

Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga akceptującej język:

Zmodyfikuj, ewentualnie, tę konstrukcję aby udowodnić, że NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego przeprowadź weryfikację w trzech etapach: konstrukcja słów , gdzie (wyrocznia), sklejanie, weryfikacja, czy .


ZADANIA DOMOWE


Ćwiczenie 6

Uzasadnij, że jeśli funkcja jest konstruowalna pamięciowo, to obliczenie z definicji konstruowalności pamięciowej (tzn. , ) następuje w co najwyżej krokach, gdzie jest pewną stałą niezależną od .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 7

Uzasadnij, że funkcja jest konstruowalna pamięciowo.