Klasy problemów NP

Wprowadzenie

Cała klasa problemów o złożoności czasowej wielomianowej lub większej, uznawana jest za ciekawy obszar do prowadzenia wszelkich badań naukowych. Dla wspomnianych problemów postanowiono więc utworzyć kolejne zagadnienia, które umożliwiłyby precyzyjniejsze określanie poziomu trudności danego problemu. Zagadnienia te przyjęły następujące nazewnictwo:

• problem P;
• problem NP;
• problem NP-zupełny;
• problem NP-trudny.

Znaczenie poszczególnych zagadnień zostanie wyjaśnione w dalszej części niniejszego rozdziału.

Problem NP

Problemami klasy NP nazywamy problemy decyzyjne w których sprawdzenie poprawności określonego rozwiązania wymaga złożoności obliczeniowej wielomianowej. Z powyższego stwierdzenia wynika więc, że znalezienie rozwiązania dla problemów NP wymaga złożoności co najmniej wielomianowej.

Warto również wiedzieć, że w klasie problemów NP zawierają się problemy P oraz problemy NP zupełne.

Problem P

Problemami klasy P nazywamy problemy decyzyjne w których znalezienie rozwiązania wymaga złożoności obliczeniowej wielomianowej. Problemy P należą do zbioru problemów NP. Z tego wynika, że:

• sprawdzenie poprawności rozwiązania danego problemu jest możliwe w czasie wielomianowym;
• znalezienie rozwiązania danego problemu jest możliwe również w czasie wielomianowym.

Problem NP-zupełny

Problemami klasy NP-zupełnej nazywamy problemy decyzyjne w których znalezienie rozwiązania nie jest możliwe w czasie wielomianowym. Problemy NP-zupełne należą do zbioru problemów NP jak również do zbioru problemów NP-trudnych. Z tego wynika, że:

• sprawdzenie poprawności rozwiązania danego problemu jest możliwe w czasie wielomianowym;
• znalezienie rozwiązania danego problemu nie jest możliwe w czasie wielomianowym.

Problemy NP-zupełne można zaprezentować następująco:

Problem NP-trudny

Problemami klasy NP-trudnej nazywamy problemy obliczeniowe dla których znalezienie rozwiązania problemu nie jest możliwe ze złożonością wielomianową oraz sprawdzenie rozwiązania problemu jest co najmniej tak trudne jak każdego innego problemu NP. Problemy NP-Trudne obejmują zarówno problemy decyzyjne jak również problemy przeszukiwania czy też problemy optymalizacyjne. Problemy zaliczane są do NP-Trudnych jeżeli sprawdzenie poprawności rozwiązania wymaga złożoności obliczeniowej co najmniej wielomianowej i jednocześnie spełniony jest co najmniej jeden z poniższych warunków:

• rozważany problem NP jest problemem NP-Zupełnym;
• rozważany jest problem przeszukiwania;
• rozważany jest problem optymalizacyjny;
• znalezienie rozwiązania problemu nie jest możliwe ze złożonością wielomianową.

Podsumowanie

Klasy problemów NP obejmują najtrudniejsze problemy złożoności czasowej algorytmów. Podsumowaniem tematyki klasy problemów NP jest tabela reprezentująca ich zależności w stosunku do klas złożoności czasowej.