Problem decyzyjny (teoria obliczeń)
Z Wikipedii
W teorii obliczeń problem decyzyjny to pytanie sformułowane w systemie formalnym na które możliwe są 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. Teoria rekursji definiuje również hierarchię dla problemów których nie da się algorytmicznie rozwiązać, określając stopień ich "nierozwiązywalności" jako stopień Turinga.
Teoria obliczeń zwykle skupia się na problemach decyzyjnych, które są najprostsze w analizie. Odpowiednie twierdzenia przenoszą się również na problemy funkcyjne, dzięki opisanej niżej redukcji.
[edytuj] 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. W pozostałych przypadkach problem jest nierostrzygalny.
[edytuj] 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.
[edytuj] 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.
