problem decyzyjny

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ę – 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 . 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.