otsustusprobleemide

Otsustusprobleemide on küsimused, millele saab vastata jah või ei. Formaalselt võib neid käsitleda kui kehas Σ* olevat alamkogumit L, kus x∈L tähistab jah-situatsiooni. Otsustusprobleem on decidable, kui selle jaoks on lõppev algoritm, mis kõigil sisenditel lõpetab ja vastab jah või ei sõltuvalt sellest, kas x kuulub L. Kui algoritm lõpetab ainult jah-siinud ja võib lõpmatult kulgeda teistel juhtudel, on probleem rekursiivselt loetav ehk semi-deciding, kuid mitte decidable.

Otsustusprobleemide keerukust hinnatakse ressursside piiratuse järgi, näiteks ajaga ja mälu kasutusega. Peamised klassid on P (probleemid, mida lahendatakse polüaegselt deterministilise Turingi masinaga) ning NP (probleemid, mille jah-sid võid kontrollida polüaegse tõendiga). NP-kõrgus puudutab probleeme, mille lahenduse kontrollimine on polüaegne; NP-kompleetsed probleemid on nii NP-s kui ka kõigi teiste NP-probleemide polüaegselt lahendatavateks muundatavad. Huvipakkuvad näited on SAT (taotluse täitmise otsustusprobleem) ning 3-SAT, mis on NP-kompleksed; grafi värvimine ja klique on samuti NP-kõrgusega probleeme.

Halvimal juhul on mõnda otsustusprobleemi lahendamine võimatu lõplikult; peatumisprobleem (halt) on klassikaline näide undecidable’st probleemist. Sellised tulemused, mida illustreerib réduktsiooteoreemid, eristavad decidable ja undecidable probleemid. Võimalus alustada mõningaid optiimisega seotud küsimusi otsustusvormis tekib, kui näiteks küsida kas lahenduse kvaliteet on vähemalt teatud väärtus. Otsustusprobleemide uurimine on keskne osa teoreetilisest arvutus- ja computability-teooriast ning mõjutab laialdaselt teisi infotehnoloogia valdkondi.