Rozhodovací problém
otázka s odpovědí ano-ne / From Wikipedia, the free encyclopedia
Rozhodovací problém je v informatice, speciálně v teorii složitosti a teorii vyčíslitelnosti, otázka v nějakém formálním systému s odpovědí ANO-NE v závislosti na hodnotě vstupu. Například, problém „pro dvě čísla x a y, dělí x hodnotu y beze zbytku?“ je rozhodovací problém, kde odpověď „ANO“ nebo „NE“ závisí na vstupech.
Rozhodovací problémy se typicky a přirozeně objevují v otázkách rozhodnutelnosti, kdy se ptáme, zda existuje efektivní metoda pro určení existence nějakých matematických objektů nebo pro jejich příslušnost do nějaké množiny. Některé problémy v matematice jsou nerozhodnutelné.
Rozhodovací problém je jednoduchá forma obecnějšího výpočetního problému, který může vracet obecnější odpovědi než jednoduché ANO-NE. Záleží na přesné formulaci otázky, příbuzné problémy k výše uvedenému příkladu jsou „pro dvě čísla x a y, jaký je podíl y/x“ a „pro dané y, jaký je nejmenší netriviální dělitel y“. Druhý příklad je formulován jako optimalizační problém důležitý a používaný v praxi, který hledá nejlepší odpověď na danou otázku podle nějakého kritéria (taky nazývaného kriteriální funkce).
Metoda pro řešení rozhodovacího problému, zadaná ve formě algoritmu, se nazývá rozhodovací procedura pro příslušný problém. Rozhodovací problém, který lze vyřešit algoritmem, se nazývá rozhodnutelný. Známý nerozhodnutelný problém je problém zastavení.
Rozhodovací problémy se zařazují do tříd složitosti (v teorii složitosti) nebo Turingovských stupňů (v teorii rekurze), které kategorizují obtížnost vlastní tomuto problému.
Výzkum v teorii vyčíslitelnosti se typicky zaměřuje na rozhodovací problémy, protože nedochází ke ztrátě obecnosti (tzv. BÚNO).