Rodzaje problemów obliczeniowych

Zanim zostanie omówiona teoria z zakresu klasy problemów NP należy jeszcze wspomnieć po krótce o rodzajach problemów obliczeniowych rozpatrywanych w algorytmice. Generalnie rzecz biorąc istnieją trzy rodzaje problemów:

• problemy decyzyjne;
• problemy przeszukiwania;
• problemy optymalizacyjne.

Wyjaśnienie znaczenia poszczególnych zagadnień znajduje się poniżej.

Problemy decyzyjne

Problemy decyzyjne są to takie problemy, które opisano w taki sposób, że dla podanych danych wejściowych, rozwiązaniem jest zawsze prawda lub fałsz.

Problemy przeszukiwania

Problemy przeszukiwania są to takie problemy, które opisano w taki sposób, że dla podanych danych wejściowych, rozwiązaniem jest zbiór wyników spełniający warunki wynikające z opisu problemu. Wynikiem może być również zbiór pusty, jeżeli nie znaleziono wyników spełniających założeń.

Problemy optymalizacyjne

Problemy optymalizacyjne są to takie problemy, które opisano w taki sposób, że dla podanych danych wejściowych, rozwiązaniem jest najlepszy możliwy do uzyskania wynik. Reguła na podstawie której dokonujemy oceny jakości rozwiązania nazywana jest funkcją kosztu. Funkcja kosztu może być nazwana maksymalizującą (jeżeli celem funkcji kosztu jest znalezienie wartości największej) bądź minimalizującą (jeżeli celem funkcji kosztu jest znalezienie wartości najmniejszej).