Problemy trudnorozwiązywalne 1

PROBLEMY TRUDNOROZWIĄZYWALNE

Mamy całą gamę problemów tzw. t ru d n o ro z wi a z v wa I n v c h. Wszystkie one mają złożoność wykładnicza typu O fK^NT Najgorsze jest to, że maia one ograniczenie dolne liniowe O INI. a nie udało się znaleźć żadnego konkretnego algorytmu o ograniczeniu lepszym niż ponadwielomianowe. Luka algorytmiczna jest wiec tutaj olbrzymia. Klasę takich problemów nazywamy klasą NPC. Należą tu problemy z dziedzin takich jak kombinatoryka. badania operacyjne, ekonomia, teoria grafów i logika. Należą tu też probierni typu ułożeń dwuwymiarowych, czyli różnica układanki, gdzie kilka lub kilkanaście figur o nieregularnych kształtach trzeba ułożyć w jeden prostokąt lub kilka kwadratów, na bokach których wydrukowane sa dolne i górne połowy kolorowych postaci i trzeba je tak ułożyć, aby po zetknięciu krawędzi połowy postaci pasowały do siebie a kolory były identyczne ftzw. małpia układanka). Mają one złożoność O (N!)

Należą tu też problemy znajdowania dróg należące do teorii grafów — np. problem komiwojażera, który musi odwiedzić kilka miast i wrócić — też złożoność O (N!) — chodzi o znalezienie najkrótszej jego drogi.

Innymi sa problemy szeregowania i dopasowania — problem układania planu lekcji — wiemy kiedy nauczyciel może, godziny, kiedy można przeprowadzić lekcje (np. dostępność sal) i liczby godzin zajęć do przeprowadzenia przez tego samego nauczyciela z każda klasą.

Należy też tutaj problem ustalania prawdy logicznej w tzw. rachunku zadań i koloroyyanie map i grafów.

Problemy te charakteryzuje (tak, jak widać to najlepiej na przykładzie układanek), że maia one wiele rozwiązań częściowych i tylko kilka lub nawet iedno właściwe pełne rozwiązanie. Nie ma jednak deterministycznej procedury przeglądającej wszystkie dostępne możliwości.

Rozwiązania trzeba odgadnąć. Jeśli je odgadniemy i zapamiętamy sposób dojścia, to powtórzymy to bardzo szybko. Zatem taki niedeterministyczny algorytm ma rozwiązanie o czasie wielomianowym.

Mówimy, że każdy problem NPC ma niedeterministyczny algorytm o czasie wielomianowym (Nondeterministic Pofynomial) — tylko trzeba takie "magiczne" rozwiązania znaleźć.

Oprócz posiadania deterministycznego rozwiązania, którego nie da się znaleźć w rozsądnym czasie i "magicznego" niedeterministycznego rozwiązania, które da się znaleźć w rozsądnym czasie problemy NPC maia te własność, że sa ze sobą powiązane. Albo wszystkie problemy NPC sątrudnorozwiązywalne, albo żaden z nich nie jest. Tę własność nazywa się zupełnością (Comolete) — Rozszyfrowaliśmy skrót NPC. Są to problemy NP — zupełne.

Jakie są konsekwencje takiego stwierdzenia: czyli zupełności?

Jeśli ktoś udowodni wykładnicze dolne ograniczenie dla jakiegokolwiek problemu NP. — zupełnego, to obowiązuje ono dla wszystkich. Jeśliby ktoś znalazł wielomianowy algorytm dla jednego, to będzie on dobry dla wszystkich. Twierdzenie to da się udowodnić.

Jaka jest relacja między NP a P?

Czy istnieją problemy istotnie trudnorozwiązywalne?

NP — problemy o niedeterministycznych algorytmach o czasie wielomianowym P — problemy łatworo z wiązy walne — czyli mające rozwiązanie wielomianowe

Jeśli jakiś problem z NP okaże się łatwy, czyli będzie należał do P, to wszystkie problemy klasy NP będą należały do P, czyli NP = P. Czyli, że sąto rzeczywiście łatwo rozwiązywalne, tylko trzeba znaleźć ten jeden kluczowy. Problem ten został sformułowany w 1971 r. i do dziś jest nierozstrzygnięty. Obecnie raczej skłaniamy się do poglądu, że NP ł P czyli, że sa problemy trudnorozwiązywalne!

Ponadto można pokazać, że są problemy należące do NP, ale nie NP — zupełne. Takim problemem jest sprawdzanie czy dana liczba jest liczba pierwsza. Dla problemów NP nawet znalezienie, że jeden z nich jest wielomianowy (klasy P) nie oznacza, że wszystkie są tej klasy, czyli że zachodzi NP = P.