Rozhodovací problém - Decision problem
V teorii vypočítatelnosti a teorii výpočetní složitosti je rozhodovací problém problém, který lze považovat za otázku ano - ne o vstupních hodnotách. Příkladem rozhodovacího problému je rozhodnutí, zda je dané přirozené číslo prvočíslo . Dalším problémem je problém „pokud dáme dvě čísla x a y , x rovnoměrně rozdělí y ?“. Odpověď je „ano“ nebo „ne“ v závislosti na hodnotách x a y . Metoda řešení rozhodovacího problému, daná ve formě algoritmu , se nazývá rozhodovací postup pro tento problém. Postup rozhodování pro rozhodovací problém „dané dvě čísla x a y , má x rovnoměrně rozdělit y ?“ by dal kroky k určení, zda x rovnoměrně rozděluje y . Jedním z takových algoritmů je dlouhé dělení . Pokud je zbytek nula, odpověď je „ano“, jinak je „ne“. Rozhodovací problém, který lze vyřešit pomocí algoritmu, se nazývá rozhodnutelný .
Problémy s rozhodováním se obvykle objevují v matematických otázkách rozhodovatelnosti , tj. V otázce existence účinné metody k určení existence nějakého objektu nebo jeho členství v množině; některé z nejdůležitějších problémů v matematice jsou nerozhodnutelné .
Pole výpočetní složitosti kategorizuje rozhodovatelné rozhodovací problémy podle toho, jak obtížně se řeší. „Obtížný“ je v tomto smyslu popsán z hlediska výpočetních zdrojů potřebných nejúčinnějším algoritmem pro určitý problém. Pole teorie rekurze mezitím kategorizuje nerozhodnutelné rozhodovací problémy podle Turingova stupně , což je měřítkem nepočitatelnosti vlastní každému řešení.
Definice
Rozhodovací problém je ano-or-no na otázku nekonečné množiny vstupů. Je tradiční definovat rozhodovací problém jako soubor možných vstupů společně se sadou vstupů, pro které je odpověď ano .
Těmito vstupy mohou být přirozená čísla, ale mohou to být také hodnoty nějakého jiného druhu, například binární řetězce nebo řetězce přes jinou abecedu . Podmnožinou řetězců, pro které problém vrací „ano“, je formální jazyk a problémy s rozhodováním jsou často definovány jako formální jazyky.
Pomocí kódování, jako je Gödelovo číslování , lze libovolný řetězec kódovat jako přirozené číslo, pomocí kterého lze definovat problém s rozhodováním jako podmnožinu přirozených čísel. Proto je algoritmem rozhodovacího problému spočítat charakteristickou funkci podmnožiny přirozených čísel.
Příklady
Klasickým příkladem rozhodovatelného rozhodovacího problému je sada prvočísel. Testováním všech možných netriviálních faktorů je možné efektivně rozhodnout, zda dané přirozené číslo je prvočíslo. I když jsou známy mnohem efektivnější metody testování primality , existence jakékoli účinné metody je dostatečná pro stanovení rozhodovatelnosti.
Rozhodnutelnost
Rozhodovací problém je rozhodnutelný nebo efektivně řešitelný, pokud množina vstupů (nebo přirozených čísel), na kterou je odpověď ano, je rekurzivní množina . Problém je částečně rozhodnutelný , semidecidovatelný , řešitelný nebo prokazatelný, pokud je množina vstupů (nebo přirozených čísel), na kterou je odpověď ano, rekurzivně spočetnou množinou . Problémy, o nichž nelze rozhodnout, jsou nerozhodnutelné . Pro ty není možné vytvořit algoritmus, efektivní ani jiný, který by je řešil.
Problém zastavení je důležitým nerozhodnutelným problémem rozhodování; další příklady najdete v seznamu nerozhodnutelných problémů .
Kompletní problémy
Problémy s rozhodováním lze objednat podle mnohostranné redukovatelnosti a související s proveditelnými redukcemi, jako jsou polynomiálně-časové redukce . Rozhodnutí problém P je řekl, aby byl úplný pro množinu rozhodovacích problémů s jestliže P je členem S a každý problém S může být snížena na P . Úplné rozhodovací problémy se používají v teorii výpočetní složitosti k charakterizaci tříd složitosti rozhodovacích problémů. Například problém booleovské uspokojivosti je u třídy NP rozhodovacích problémů za polynomiálně-časové redukovatelnosti úplný .
Funkční problémy
Problémy s rozhodováním úzce souvisí s problémy s funkcemi , které mohou mít složitější odpovědi než jednoduché „ano“ nebo „ne“. Odpovídající funkční problém je „dán dvěma čísly x a y , co je x děleno y ?“.
Problém funkce se skládá z částečné funkce f ; neformálním „problémem“ je spočítat hodnoty f na vstupech, pro které je definován.
Každý funkční problém lze změnit na rozhodovací problém; rozhodovacím problémem je pouze graf přidružené funkce. (Graf funkce f je množina párů ( x , y ) taková, že f ( x ) = y .) Pokud by byl tento rozhodovací problém účinně řešitelný, pak by byl také funkční problém. Toto snížení však nerespektuje výpočetní složitost. Například je možné, aby byl graf funkce rozhodnutelný v polynomiálním čase (v takovém případě se doba běhu počítá jako funkce páru ( x , y )), když funkci nelze vypočítat v polynomiálním čase (ve kterém doba běhu případu se počítá jako funkce samotného x ). Funkce f ( x ) = 2 x má tuto vlastnost.
Každý rozhodovací problém lze převést na funkční problém výpočtu charakteristické funkce množiny spojené s rozhodovacím problémem. Pokud je tato funkce vypočítatelná, pak je rozhodující související problém s rozhodováním. Tato redukce je však liberálnější než standardní redukce používaná ve výpočetní složitosti (někdy nazývaná polynomiálně-časová redukce jedna-jedna); například složitost charakteristických funkcí NP-úplného problému a jeho doplňku k úplnému NP je úplná stejná, přestože základní rozhodovací problémy nemusí být v některých typických modelech výpočtu považovány za rovnocenné.
Problémy s optimalizací
Na rozdíl od problémů s rozhodováním, pro které pro každý vstup existuje pouze jedna správná odpověď, se optimalizační problémy týkají nalezení nejlepší odpovědi na konkrétní vstup. Problémy s optimalizací vznikají přirozeně v mnoha aplikacích, jako je problém obchodního cestujícího a mnoho otázek v lineárním programování .
Existují standardní techniky pro transformaci funkčních a optimalizačních problémů na rozhodovací problémy. Například v problému obchodního cestujícího je optimalizačním problémem vytvoření prohlídky s minimální hmotností. Rozhodnutí problém spojený je: pro každý N , aby rozhodl, zda je v grafu žádnou prohlídku s hmotností menší než N . Opakovaným zodpovězením rozhodovacího problému je možné zjistit minimální váhu prohlídky.
Protože teorie rozhodovacích problémů je velmi dobře vyvinutá, výzkum teorie složitosti se obvykle zaměřil na rozhodovací problémy. Samotné optimalizační problémy jsou stále předmětem zájmu v teorii vypočítatelnosti i v oblastech, jako je operační výzkum .
Viz také
- VŠE (složitost)
- Výpočtový problém
- Rozhodovatelnost (logika) - pro problém rozhodování, zda je vzorec důsledkem logické teorie .
- Problém s vyhledáváním
- Problém počítání (složitost)
- Slovní úloha (matematika)
Reference
- Kozen, DC (2012), Automata and Computability , Springer.
- Hartley Rogers, Jr. , The Theory of Rekurzivní funkce a efektivní vypočítatelnost , MIT Press, ISBN 0-262-68052-1 (brožovaná verze), ISBN 0-07-053522-1
- Sipser, M. (1996), Úvod do teorie výpočtu , PWS Publishing Co.
- Robert I. Soare (1987), Rekurzivně vyčíslitelné množiny a stupně , Springer-Verlag, ISBN 0-387-15299-7
- Daniel Kroening & Ofer Strichman, rozhodovací postupy , Springer, ISBN 978-3-540-74104-6
- Aaron Bradley & Zohar Manna , The Calculus of Computation , Springer, ISBN 978-3-540-74112-1