Problem decyzyjny (teoria obliczeń)
Z Wikipedii, wolnej encyclopedia
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.