Problem decyzyjny Pi- zbiór parametrów, które nie muszą mieć nadanych wartości oraz pytanie, na które odpowiedź brzmi "tak" lub "nie". Ustalając wartości parametrów danego problemu Pi otrzymujemy instancję (konkretny problem), oznaczając ją przez I.
Problem decyzyjny Pi- zbiór instancji DPi oraz jego podzbiór, który zawiera wszystkie instancje, na które odpowiedź brzmi "tak".
Problem optymalizacyjny- wymaga ekstremalizacji funkcji celu związanej z danym problemem kombinatorycznym. Dla każdego problemu optymalizacyjnego istnieje odpowiadający mu problem decyzyjny, ale nie jest na odwrót.
Problem przeszukiwania Pi definiuje się przez podanie :

1. zbioru instancji D_Pi
2. zbioru rozwiązań Z_Pi(I) dla każdej instancji I należącej do D_Pi

Algorytm A rozwiązuje problem przeszukiwania Pi, jeśli dla każdej instancji I należącej do DPi odpowiedź brzmi "nie" jeśli zbiór Z_Pi(I) jest pusty a w przeciwnym razie algorytm znajduje jedno rozwiązanie należące do Z_Pi(I).
Przykład: problem sortowania:
Instancja I - dla danego ciągu liczb naturalnych znaleźć ciąg uporządkowany rosnąco.