1. TEORIA ZŁOŻONOŚCI OBLICZENIOWEJ

Σ = {cyfry systemu, #} cyfry systemu, np 0..9 w systemie dziesiętnym, 0-1 w binarnym, 1 w unarnym; # - separator

Słowa dziesiętne: 1234, 1372, 1254; słowa binarne: 0, 1, 1100, 1010, 01; słowa unarne: 1, 11, 111

Język binarny: 0#101#01001

1. Kodowanie danych

1. Reguła kodowania danych

1. Każdą daną problemu przedstawiamy za pomocą jednego słowa danego języka Σ.

2. Kolejne dane (słowa) są oddzielone pojedynczym separatorem # i są w ustalonej kolejności

3. Jeżeli wartość dwóch danych x1 i x2 jest taka sama (x1=x2) to zarówno x1, jak i x2 są kodowane tym samym słowem.

1. Rozmiar instancji problemu. Nieefektywność.

N(I) = O(nlog_b(MAX(I))), gdzie:

N₁(I) = O(nMAX(I)) – kodowanie unarne daje wykładniczy wzrost rozmiaru problemu w stosunku do kodowania w systemie o podstawie b>=2. Musimy je odrzucić ze względu na jego nieefektywność.

• N(I) – długość łańcucha – rozmiar instancji I

• b – podstawa systemu

• MAX(I) – największa wartość w danej instancji (I)

1. Problemy decyzyjne i optymalizacyjne

Problem optymalizacyjny – problem, w którym mamy za zadanie znaleźć ekstremum jakiejś funkcji, np. problem programowania liniowego, problem plecakowy(rozmiar plecaka B, zadania j – rozmiar zadania+wartość zadania, znaleźć takie rozw, aby plecak miał jak najwyższą wartość), problem komiwojażera(N miast, macierz odległości między nimi, poruszać się tak, aby przejechać wszystkie miasta i wrócić z ostatniego do pierwszego po jak najkrótszej drodze, aby miasta nie powtarzały się)

Problem decyzyjny (rozpoznania) – problem, w którym mamy za zadanie odpowiedzieć na pytanie zadane w taki sposób, że jedynymi odpowiedziami są TAK bądź NIE, np. czy dana liczba naturalna n jest liczbą pierwszą, problem podziału, problem spełnialności wyrażeń logicznych

Twierdzenie odwrotne nie jest prawdziwe.

Jeżeli mamy parę problemów Po( problem optymalizacyjny) i Pd (odpowiadający mu problem decyzyjny, to prawdziwe są zależności:

• Jeżeli problem Pd jest łatwy, to Po również jest łatwy

• Jeżeli problem Pd jest trudny, to Po też jest trudny.

Problem maksymalizacji pr. decyzyjny , y=const

Problem minimalizacji pr. decyzyjny

1. Maszyna Turinga

1. DTM – deterministyczna maszyna Turinga

Budowa:

• Taśma nieskończonej długości, podzielona na pola, w których można zapisywać pojedyncze symbole

• Głowica zapisująco – odczytująca przesuwająca się nad taśmą

• Układ sterujący

1. NDTM – niedeterministyczna maszyna Turinga

Budowa:

• DTM

• Moduł zgadujący sterujący głowicą zapisują (Układ zgadujący + głowica zapisujaca) – zapisanie na taśmie pewnego odgadnietego rozwiązania (upakowanie plecaka, min funkcji…)

Wykonanie problemu:

• Etap zgadywania

• Etap sprawdzania

• Obliczenia zostały zaakceptowane, gdy zatrzyma się na qY, obliczenia nie zostaną zaakceptowane, gdy maszyna skończy na stanie qN lub nie zatrzyma się wcale.

1. Klasy złożoności problemów

Def. Język L należy do klasy P (wielomianowej), jeżeli istnieje algorytm wielomianowy M na DTM akceptujący ten język.
Problem decyzyjny Π należy do klasy P, jeżeli istnieje algorytm wielomianowy M na DTM rozwiązujący ten problem.
Klasa P zawiera te wszystkie problemy decyzyjne, dla których znaleziono wielomianowe algorytmy ich rozwiązania.

Def. Język L należy do klasy NP (niedeterministycznej wielomianowej), jeżeli istnieje algorytm wielomianowy M na DTM akceptujący ten język.
Problem decyzyjny Π należy do klasy NP, jeżeli istnieje algorytm wielomianowy M na NDTM rozwiązujący ten problem.
Klasa NP. zawiera te wszystkie problemy decyzyjne, dla których znaleziono ponadwielomianowe algorytmy ich rozwiązania.
Problem Π należy do klasy NP., jeżeli możliwe jest w wielomianowym czasie odgadnięcie jakiegoś rozwiązania i sprawdzenie, czy to rozwiązanie daje odpowiedź „TAK”.

Problem spełnialności wyrażeń logicznych, cykl Hamiltona…

p-wielomianowe,
np- dla których w. decyzyjna jest wielomianowa,

np-zupełne - problem jest Np., każdy inny problem zawarty w NP. jest w niego transformowalny wielomianowo silnie np-zupełne –nie ma pseudowielomianowego algorytmu rozwiązania

problem komiwojażera

1. Definicje transformacji wielomianowej i pseudowielomianowej…

1. Transformacja wielomianowa

Zapisujemy:

1. Transformacja pseudowielomianowa

1. Dowodzenie NP.-zupełności

1. Problem musi należeć do klasy NP.

1. Dowodzenie NP- trudności

2. Przynależność problemu do klasy P

Należy podać wielomianowy algorytm jego rozwiązania

1. Dowodzenie silnej NP.-zuełności

- trudne,

Inne podejście:

• Pokazać, ze problem Π należy do klasy NP.

• Wybrać inny silnie NP-zupełny problem Π’

• Dokonać transformacji pseudowielomianowej problemu Π’ w problem Π