Problem odluke

U teoriji izračunljivosti i računskoj teoriji složenosti, problem odluke je pitanje postavljeno u nekom formalnom sustavu s da/ne odgovorom. Na primjer, problem »Za dana dva broja x i y, dijeli li x y?« je problem odluke. Odgovor može biti „da” ili „ne”, i ovisi o vrijednostima x i y.

Problemi su odluke usko povezani s funkcijskim problemima, koji mogu imati složenije odgovore od jednostavnih „da” ili „ne”. Odgovarajući funkcijski problem jest »Za dana dva broja x i y, koji je rezultat dijeljenja x sa y?«. Također su povezani s optimizacijskim problemima, koji se bave pronalaženjem najboljeg odgovora za dani problem.

Metode korištene za rješavanje problema odluke se zovu postupci odluke ili algoritmi. Algoritam bi za ovaj problem odluke objasnio kako odrediti dijeli li x y, za dane x i y. Za problem odluke koji može biti riješen nekim algoritmom se kaže da je odlučiv.

Polje računske složenosti kategorizira odlučive probleme odluke po težini rješavanja. „Težina” je, u ovom smislu, opisana u terminima računskih resursa potrebnih najučinkovitijem algoritmu za određeni problem. S druge strane, polje teorije rekurzije kategorizira neodlučive probleme po Turingovom stupnju, koji je mjera neizračunljivosti inherentne svakom rješenju.

Istraživanje u teoriji izračunljivosti se obično sredotoči na probleme odluke, pri čemu ne dolazi do smanjenja općenitosti.

Nedovršeni članak Problem odluke koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.