Problem decyzyjny
Problem decyzyjny to pytanie sformułowane w formalnym systemie, na które odpowiedzią może być jedynie tak lub nie. Na przykład, pytanie „Czy x jest dzielnikiem y?” jest problemem decyzyjnym, którego odpowiedź zależy od konkretnych wartości x i y.
W odróżnieniu od problemów decyzyjnych, istnieją również problemy funkcyjne, gdzie wymagane są bardziej złożone odpowiedzi, oraz problemy optymalizacyjne, które polegają na znalezieniu najlepszego rozwiązania. Teoria złożoności obliczeniowej klasyfikuje problemy decyzyjne według trudności ich rozwiązania, analizując zasoby wymagane przez najefektywniejsze algorytmy.
Definicja
Problem decyzyjny można zdefiniować jako dowolny podzbiór A liczb naturalnych. W tym kontekście problem jest równoważny językowi formalnemu z poprawnymi rozwiązaniami. Problem jest rozstrzygalny, jeśli A jest zbiorem rekurencyjnym, częściowo obliczalny, jeśli A jest zbiorem rekurencyjnie przeliczalnym, a nierozstrzygalny, jeśli nie jest obliczalny.
Przykłady
- Problem rozstrzygalny: Zbiór liczb pierwszych, który można zweryfikować poprzez sprawdzanie potencjalnych dzielników.
- Problem nierozstrzygalny: Problem stopu, który nie ma algorytmicznego rozwiązania.
Równoważność z problemami funkcyjnymi
Problemy funkcyjne są dowolnymi częściowymi funkcjami f, które można przekształcić na problemy decyzyjne. Na przykład, dla każdej funkcji można zdefiniować jej graf jako zbiór par (x,y), gdzie f(x) = y. Choć taka redukcja nie zawsze zachowuje złożoność obliczeniową, to każdy problem decyzyjny można przekształcić w funkcyjny, wyliczając funkcję charakterystyczną zbioru akceptowanych wejść. Ta redukcja zachowuje obliczalność, chociaż dla dokładniejszych redukcji, które również uwzględniają klasy złożoności, stosuje się bardziej szczegółowe podejścia.
