Problem decyzyjny (teoria obliczeń)
Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są tylko odpowiedzi tak i nie. Przykładowo problem „Dla danych liczb x i y, czy x jest dzielnikiem y?” jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y.
Analogicznie do problemów decyzyjnych definiuje się problemy funkcyjne – na które wymagane są bardziej złożone odpowiedzi oraz problemy optymalizacyjne – polegające na znalezieniu najlepszej odpowiedzi.
Teoria złożoności obliczeniowej kategoryzuje problemy decyzyjne w zależności od tego jak trudno je rozwiązać, w terminach zasobów wymaganych przez najefektywniejsze algorytmy. Natomiast teoria rekursji definiuje również hierarchię dla problemów, których nie można algorytmicznie rozwiązać, określając stopień ich „nierozwiązywalności” jako stopień Turinga.
Teoria obliczeń zwykle skupia się na problemach decyzyjnych, ponieważ są najprostsze w analizie. Odpowiednie twierdzenia przenoszą się również na problemy funkcyjne, dzięki opisanej niżej redukcji.
Definicja
Problem decyzyjny to dowolna dwuwartościowa funkcja na nieskończonej dziedzinie. Z tego powodu zwykle definiuje się problem jako zbiór wejść, dla których wynik jest równy tak. W tym sensie problem decyzyjny jest równoważny językowi formalnemu poprawnych rozwiązań.
Formalnie, problem decyzyjny to dowolny podzbiór A liczb naturalnych. Używając numeracji Gödla można sprowadzić do takiego zbioru dowolny język formalny. Problem decyzyjny jest rozstrzygalny albo obliczalny, jeśli A jest zbiorem rekurencyjnym. Problem jest częściowo obliczalny, jeśli A jest zbiorem rekurencyjnie przeliczalnym. Problem jest nierozstrzygalny, jeśli nie jest obliczalny.
Przykłady
Klasycznym przykładem problemu rozstrzygalnego jest zbiór liczb pierwszych. Istnieje metoda sprawdzenia, czy dana liczba jest pierwsza przez sprawdzenie wszystkich jej potencjalnych dzielników. Choć istnieją znacznie efektywniejsze testy pierwszości, powyższa metoda wystarcza do pokazania, że jest to problem rozstrzygalny.
Jednym z najważniejszych przykładów problemu nierozstrzygalnego jest problem stopu.
Równoważność z problemami funkcyjnymi
Problem funkcyjny to dowolna częściowa funkcja f. Każda taka funkcja może być zamieniona na problem decyzyjny. Przykładowo dla każdej funkcji możemy zdefiniować jej graf (zbiór par (x,y), takich że f(x) = y) i rozważać go jako problem decyzyjny. Ta redukcja nie zachowuje jednak złożoności obliczeniowej – np. graf funkcji może być obliczalny w czasie wielomianowym, podczas gdy sama funkcja nie (licząc w stosunku do długości wejścia). Taką własność ma np. funkcja f(x) = 2x.
Każdy problem decyzyjny można również zamienić na funkcyjny, wyliczając funkcję charakterystyczną zbioru akceptowanych wejść. Ta redukcja zachowuje obliczalność, ale w praktyce stosuje się bardziej dokładne redukcje zachowujące również klasy złożoności. W tej redukcji przykładowo funkcje charakterystyczne klasy NP są tym samym, co funkcje charakterystyczne klasy Co-NP, mimo że odpowiadające im klasy problemów decyzyjnych są uważane za różne.