Problem odluke
U teoriji izračunljivosti i teoriji kompleksnosti, problem odlučivanja je pitanje u nekom formalnom sistemu, koje daje odgovor DA ili NE. Na primer, problem data su dva broja x i y. Da li x deli y? je problem odlučivanja. Odgovor može biti ili DA ili Ne, u zavisnosti od vrednosti x i y.
Problemi odlučivanja su blisko povezani sa funkcijskim problemima, koji mogu da daju odgovore koji su složeniji od prostog DA ili NE. Odgovarajući funkcijski problem bi mogao biti ako su data dva broja x i y, koji je razultat deljenja x sa y?". Takođe su povezani sa optimizacionim problemima, koji se bave pronalaženjem najboljeg rešenja za dati problem.
Metode koje se koriste za rešavanje problema odlučivanja se nazivaju procedurama za odlučivanje ili algoritmima. Algoritam za problem odlučivanja data su dva broja x i y, da li x deli y?" bi objasnio kako da se odredi da li x deli y, za dato x i y. Jedan takav algoritam (za deljenje brojeva) deca uče u školi. Ako problem odlučivanja može da se reši nekim algoritmom, kažemo da je odlučiv.
Oblast računske složenosti kategoriše probleme odlučivanja po tome koliko su teški za rešavanje. Teški u ovom smislu podrazumeva koliko je računarskih resursa potrebno za najefikasniji algoritam za određeni problem. Oblast teorije rekurzije, sa druge strane, kategoriše neodlučive probleme odlučivanja Tjuringovim stepenom.
Proučavanja u teoriji izračunljivosti se obično baziraju na problemima odlučivanja. U ovom slučaju nemam gubitka u opštosti razmatranja u odnosu na funkcijske probleme.
Definicija[uredi | uredi kod]
Problem odlučivanja je proizvoljno da-ne pitanje na beskonačnom skupu ulaza. Zbog ovoga, tradicionalno se problemi odlučivanja definišu u smislu skupa ulaza za koje problem vraća odgovor DA. U ovom smislu, problem odlučivanja je ekvivalentan formalnom jeziku.
Formalno, problem odlučivanja je podskup A prirodnih brojeva. Korišćenjem Gedelovih brojeva, moguće je proučavati i druge skupove kao formalne jezike. Neformalno, problem se sastoji u određivanju da li je dati broj u skupu.
Problem odlučivanja se naziva odlučivim ili efektivno rešivim ako je A rekurzivan skup. Problem se naziva parcijalno odlučivim, poluodlučivim, rešivim, ili dokazivim ako je A rekurzivno prebrojiv skup. Parcijalno odlučivi problemi i svi ostali problemi koji nisu odlučivi se nazivaju neodlučivim.