beslutsproblem

Beslutsproblem är problem som formuleras som ett ja/nej-svar för varje indata. Indatan är vanligtvis en sträng över ett finit alfabet och målet är att bestämma om svaret är ja eller nej för just den strängen. Om det finns en algoritm som alltid avslutas och ger korrekt ja- eller nejbeslut för alla möjliga indatan, sägs problemet vara beslutsbart. Om ingen sådan algoritm finns sägs problemet vara obestägbart eller odeciderat.

En viktig relaterad skillnad är begreppet rekursivt uppräkneligt (semi-decidabelt). Ett problem är rekursivt uppräkneligt om det finns en algoritm som, för varje ja-instans, avslutas och accepterar, medan den kan fortsätta köra utan att avslutas för nej-instansen. Många obestämbara problem kan vara rekursivt uppräkneliga, medan de inte kan avgöras i allmänhet.

Historiskt var beslutsproblemet centralt i Hilberts program. Entscheidungsproblemet frågade om det finns ett generellt algoritmiskt sätt att avgöra sanningen i varje första ordningens logik-sats. År 1936 visade Church och Turing oberoende att sådant allmänt algoritmiskt beslut är omöjligt; vissa problem är obestämbara.

Exempel på beslutsproblem. Halting-problemet är obestägbart: det finns ingen algoritm som avgör för alla program och ingångar om de avslutas. SAT (satsen att en Boolean-formel är satisfierbar) är beslutsbart och NP-fullständigt. Post-korrespondens-problemet är obestägbart. Genom reduktioner kan man visa att ett problem är obestägbart genom att reducera ett känt obestämbart problem till det.

Beslutsproblem används inom logik, beräkningsteori och formella språk för att klassificera vad som är faktiskt beräkneligt och vad som inte kan avgöras av ett generellt algoritmiskt sätt.