Проблем одлучивања
У теорији израчунљивости и теорији комплексности, проблем одлучивања је питање у неком формалном систему, које даје одговор ДА или НЕ. На пример, проблем дата су два броја x и y. Да ли x дели y? је проблем одлучивања. Одговор може бити или ДА или Не, у зависности од вредности x и y.
Проблеми одлучивања су блиско повезани са функцијским проблемима, који могу да дају одговоре који су сложенији од простог ДА или НЕ. Одговарајући функцијски проблем би могао бити ако су дата два броја x и y, који је разултат дељења x са y?". Такође су повезани са оптимизационим проблемима, који се баве проналажењем најбољег решења за дати проблем.
Методе које се користе за решавање проблема одлучивања се називају процедурама за одлучивање или алгоритмима. Алгоритам за проблем одлучивања дата су два броја x и y, да ли x дели y?" би објаснио како да се одреди да ли x дели y, за дато x и y. Један такав алгоритам (за дељење бројева) деца уче у школи. Ако проблем одлучивања може да се реши неким алгоритмом, кажемо да је одлучив.
Област рачунске сложености категорише проблеме одлучивања по томе колико су тешки за решавање. Тешки у овом смислу подразумева колико је рачунарских ресурса потребно за најефикаснији алгоритам за одређени проблем. Област теорије рекурзије, са друге стране, категорише неодлучиве проблеме одлучивања Тјуринговим степеном.
Проучавања у теорији израчунљивости се обично базирају на проблемима одлучивања. У овом случају немам губитка у општости разматрања у односу на функцијске проблеме.
Дефиниција
уредиПроблем одлучивања је произвољно да-не питање на бесконачном скупу улаза. Због овога, традиционално се проблеми одлучивања дефинишу у смислу скупа улаза за које проблем враћа одговор ДА. У овом смислу, проблем одлучивања је еквивалентан формалном језику.
Формално, проблем одлучивања је подскуп A природних бројева. Коришћењем Геделових бројева, могуће је проучавати и друге скупове као формалне језике. Неформално, проблем се састоји у одређивању да ли је дати број у скупу.
Проблем одлучивања се назива одлучивим или ефективно решивим ако је A рекурзиван скуп. Проблем се назива парцијално одлучивим, полуодлучивим, решивим, или доказивим ако је A рекурзивно пребројив скуп. Парцијално одлучиви проблеми и сви остали проблеми који нису одлучиви се називају неодлучивим.