Można przypuszczać, że tak duży koszt rozwiązania zadania "wież Hanoi", czy zadania "permutacje" wiąże się z długim rozwiązaniem i tylko takie problemy zabierają "nierozsądnie" dużo czasu. Ale tak nie jest. Istnieje wiele problemów, których rozwiązanie jest bardzo krótkie, a mimo to czas potrzebny do wygenerowania tego rozwiązania jest niedopuszczalnie duży.

Definicja 2.1 Problemem decyzyjnym nazywamy taki problem, którego rozwiązaniem są słowa "tak" lub "nie".

Danych jest n kwadratowych kart, gdzie n jest kwadratem liczby naturalnej. W każdej z czterech części karty, wyznaczonej przez przekątne, wydrukowane są fragmenty kolorowych obrazków. Niektóre obrazki można złożyć razem (tak, jak w dziecinnej układance), inne nie pasują do siebie. Problem polega na tym, by zbadać, czy z danych n kart można ułożyć kwadrat tak, by wszystkie obrazki pasowały kształtem i kolorem, por. D. Harel, rzecz o istocie informatyki. Algorytmika, WNT, 1987.

Niech rozwiązaniem zadania będzie słowo "tak", gdy istnieje takie ułożenie i słowo "nie", gdy nie można z danych kart ułożyć kwadratu o wymaganych własnościach. Załóżmy dodatkowo, że karty mają ustaloną orientację i nie można ich obracać. Jest to więc problem decyzyjny. Na przykład dla kart przedstawionych na rysunku 15.2(a) nie ma rozwiązania z odpowiedzią "tak" dla dowolnej liczby n, a dla kart przedstawionych na rysunku 15.2(b) istnieje rozwiązanie z odpowiedzią "tak", jak pokazano na rysunku 15.2(c).

Naiwny algorytm rozwiązania tego problemu polega na przeglądaniu wszystkich możliwych ułożeń. Dla każdego konkretnego ułożenia kart, algorytm sprawdza, czy ułożenie jest poprawne. I chociaż samo sprawdzenie konkretnego ułożenia ma koszt liniowy, to liczba ułożeń powoduje, że koszt algorytmu naiwnego wynosi O(n!). Aby przejrzeć 25! ułożeń, algorytm pracowałby 400 milionów lat na średnio szybkim komputerze.

Jest to jeden z najbardziej znanych i ważnych problemów. Rozważamy klasyczny rachunek zdań. Poprawne wyrażenia tego rachunku, tzn. formuły, można zdefiniować następująco:

formuła ::= zmienna| (formuła Ù formuła)| (formuła Ú formuła)| (formuła Þ formuła)| Ø formuła

Mając dane wartości zmiennych, tzw. wartościowanie, możemy pytać, czy podana formuła jest, czy nie jest prawdziwa przy tym wartościowaniu.

Problem spełnialności polega na sprawdzeniu, czy dana formuła posiada chociaż jedno wartościowanie (jeden zestaw wartości zmiennych), przy którym jej wartością jest prawda. Na przykład, formuła Ø ((p Ù q) Þ r) Ù (r Ú (p Þ Ø q)) nie jest spełnialna, przy dowolnym wartościowaniu zmiennych wartością formuły jest fałsz. Natomiast formuła (Ø (p Þ q) Ù (q Ú (r Þ Ø p)) jest spełnialna, bo np. przy wartościowaniu w(p) = 1, w(q) = 0, w(r) = 0, wartością formuły jest true.

Wszyscy znają metodę zerojedynkową badania, czy formuła rachunku zdań jest prawdziwa, czy nie. Ta bardzo prosta metoda ma jednak koszt wykładniczy względem długości formuły: w najgorszym przypadku trzeba sprawdzić wszystkie wartościowania, a tych możliwych wartościowań jest 2ⁿ, gdzie n jest liczbą zmiennych. W problemie spełnialności, nie zależy nam na wskazaniu tego wartościowania, ale tylko na stwierdzeniu, czy istnieje, czy nie. Jest to problem decyzyjny.

Wymienione do tej pory przykłady problemów decyzyjnych charakteryzowały się tym, że nie są dla nich znane żadne rozwiązania o koszcie wielomianowym, oraz tym, że sprawdzenie, czy dane rozwiązanie jest poprawne można zrealizować z kosztem wielomianowym. Ponadto nie wiadomo, czy te problemy rzeczywiście wymagają czasu ponadwielomianowego. O takich problemach mówimy, że są niedeterministyczne o czasie wielomianowym. Przyjmijmy następującą definicję.

Definicja 2.2 Klasa P jest klasą problemów decyzyjnych, dla których istnieje wielomianowy algorytm rozwiązywania. Klasa NP, to klasa problemów decyzyjnych, dla których dowód, że podane rozwiązanie jest poprawne, można zweryfikować w czasie wielomianowym.

Klasę NP (N od "niedeterminizm", P od "wielomain") można scharakteryzować inaczej, jako klasę tych problemów decyzyjnych, które można rozwiązać algorytm niedeterministycznym w czasie wielomianowym. Zauważmy, że klasy P i NP nie stanowią podziału problemów decyzyjnych. Co więcej, każdy problem decyzyjny, dla którego znany jest algorytm rozwiązujący w czasie wielomianowym należy też do klasy NP : sprawdzenie poprawności rozwiązania można zrobić w czasie wielomianowym. Mamy więc P Í NP.

Do klasy NP należy wiele znanych problemów dotyczących grafów. Wymienimy tu trzy z nich: problem komiwojażera, problem ścieżek Hamiltona, problem kolorowania grafu.

Dany jest graf niezorientowany, spójny G = <V, E>, |V| = n oraz funkcja kosztu dla krawędzi c: E -> R+. Wierzchołki grafu interpretować będziemy jako miejscowości, a krawędzie jako łączące je drogi. Funkcja kosztu c, przypisuje każdej drodze jej długość. Zadaniem komiwojażera jest odwiedzić wszystkie miejscowości i wrócić do punktu wyjścia, w taki sposób, by całkowita długość pokonanej drogi była najmniejsza.

Na rysunku 15.3(a) przedstawiono przykładowy graf i cykl komiwojażera o minimalnym koszcie.

Ten sam problem można zdefiniować jako zadanie znalezienia najkrótszej drogi przechodzącej przez wszystkie wierzchołki danego niezorientowanego grafu. W wersji decyzyjnej problem ten brzmi: Czy dla danego k istnieje cykl przechodzący przez wszystkie wierzchołki grafu, taki że suma kosztów jego krawędzi jest niewiększa niż k?

Wbrew pozorom nie jest to problem błahy i nie jest to problem czysto teoretyczny. Warianty tego problemu pojawiają się w układach scalonych, w sieciach telefonicznych, w planowaniu linii montażowych i w robotyce.

Najprostsze rozwiązanie polega na przeszukiwaniu wszystkich możliwych cykli. Jeśli algorytm znajdzie cykl o koszcie co najwyżej k, zatrzymuje się i daje odpowiedź "tak". Jeśli takiego cyklu nie ma, algorytm odpowiada "nie". W przypadku grafu 15.3(a), dla k=28 odpowiedzią jest "tak", a w przypadku grafu 15.3(b), w którym wagi wszystkich krawędzi wynoszą 1, a k= 12 odpowiedzią jest "nie".

Koszt algorytmu naiwnego dla grafu o n wierzchołkach wynosi O(n!) i nie jest znane żadne wielomianowe rozwiązanie tego problemu. Oczywiście, gdyby jakaś wyrocznia wskazała nam właściwy cykl, to łatwo ( z kosztem liniowym) sprawdzilibyśmy, czy koszt tego cyklu jest niewiększy niż k i, czy to jest rzeczywiście cykl przechodzący przez wszystkie wierzchołki. Wniosek: problem komiwojażera należy do klasy NP.

Dany jest graf niezorientowany G =<V, E>. Pytamy, czy istnieje w tym grafie cykl (ew. ścieżka) przechodząca przez każdy wierzchołek grafu i to przez każdy dokładnie raz?

Na rysunku 15.3(b) przedstawiono graf i ścieżkę Hamiltona. Graf na rysunku 15.3(b) nie ma cyklu Hamiltona, natomiast graf na rysunku 15.3(a) ma wiele różnych cykli Hamiltona. Algorytm naiwny, jak się domyślamy, analizuje n! możliwych ścieżek. Jego koszt jest więc bardzo duży. Sprawdzenie natomiast, czy dana ścieżka przechodzi przez wszystkie wierzchołki i przez każdy tylko raz, może być zrealizowane z kosztem liniowym. Niestety, żadne rozsądne rozwiązanie problemu cyklu Hamiltona nie jest do tej pory znane. Problem Hamiltona należy do problemów NP.

Warto tu zauważyć, że problem Eulera, znalezienia takiej drogi (albo cyklu) w grafie, która przechodzi przez wszystkie krawędzie i to przez każdą tylko raz, chociaż wydaje się być zadaniem bardzo podobnym, to jednak nie jest. W 1736 roku, Euler znalazł wielomianowe rozwiązanie zadania:

Pytanie 4: Jaki jest koszt powyższego algorytmu znajdowania ścieżki Eulera, jeśli graf jest dany w postaci tablicy list incydencji?

Dla ustalonej liczby k, zbadać, czy dany graf można pokolorować k barwami, tak by sąsiadujące ze sobą wierzchołki (tzn. połączone krawędzią) miały różne kolory.

Różne wersje tego problemu były znane i badane od wielu lat. W 1852 roku sformułowano tzw. problem czterech barw: czy dowolną mapę można pokolorować czterema barwami, tak by dwa sąsiadujące państwa miały różne kolory. Przez 120 lat nikt nie mógł udowodnić, że cztery barwy wystarczą, ale też nikt nie umiał znaleźć przykładu mapy, którą trzeba by pokolorować pięcioma kolorami. Problem został rozwiązany pozytywnie dopiero w 1976 roku za pomocą komputera. Pytanie, czy dowolną mapę (graf płaski) można pokolorować czterema barwami, ma odpowiedź "tak". Pytanie, czy graf płaski można pokolorować dwoma kolorami ma łatwe rozwiązanie. Jest natomiast zaskakujące, że dla trzech kolorów nie jest znany żaden algorytm o koszcie wielomianowym. Podobnie jest w przypadku sformułowanego powyżej problemu decyzyjnego: wszystkie znane algorytmy badania, czy dana liczba k barw wystarczy do pokolorowania danego grafu są wykładnicze. Problem kolorowania należy do klasy NP.

Pytanie 5: Ile kolorów jest konieczne, aby pokolorować dowolne drzewo o n wierzchołkach?