Проблем одлучивања
From Wikipedia, the free encyclopedia
У теорији израчунљивости и теорији комплексности, проблем одлучивања је питање у неком формалном систему, које даје одговор ДА или НЕ. На пример, проблем дата су два броја и . Да ли дели ? је проблем одлучивања. Одговор може бити или ДА или Не, у зависности од вредности и .
Проблеми одлучивања су блиско повезани са функцијским проблемима, који могу да дају одговоре који су сложенији од простог ДА или НЕ. Одговарајући функцијски проблем би могао бити ако су дата два броја и , који је разултат дељења са ?". Такође су повезани са оптимизационим проблемима, који се баве проналажењем најбољег решења за дати проблем.
Методе које се користе за решавање проблема одлучивања се називају процедурама за одлучивање или алгоритмима. Алгоритам за проблем одлучивања дата су два броја и , да ли дели ?" би објаснио како да се одреди да ли дели , за дато и . Један такав алгоритам (за дељење бројева) деца уче у школи. Ако проблем одлучивања може да се реши неким алгоритмом, кажемо да је одлучив.
Област рачунске сложености категорише проблеме одлучивања по томе колико су тешки за решавање. Тешки у овом смислу подразумева колико је рачунарских ресурса потребно за најефикаснији алгоритам за одређени проблем. Област теорије рекурзије, са друге стране, категорише неодлучиве проблеме одлучивања Тјуринговим степеном.
Проучавања у теорији израчунљивости се обично базирају на проблемима одлучивања. У овом случају немам губитка у општости разматрања у односу на функцијске проблеме.