Rozhodovací problém

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 , 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“. +more 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ý. +more 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).

Zadání

Rozhodovací problém je libovolná otázka typu ANO-NE na nekonečné množině vstupů. Tradičně se definuje ekvivalentně jako podmnožina vstupů, na které je odpověď ANO. +more Tuto podmnožinu určuje charakteristická funkce, která v obecnosti nemusí být algoritmizovatelná.

Množina vstupů je často jednoduchá a složené či složité vstupy (grafy, matice, dvojice) se zakódují. Takto je vstupem přirozené číslo, řetězec nad binární abecedou {0,1} anebo obecněji nad nějakou konečnou množinou symbolů. +more V teorii formálních jazyků je podmnožina řetězců s odpovědí ANO jazyk odpovídající danému problému. Konkrétní vstup problému se nazývá instance problému.

Pomocí Gödelova číslování lze libovolný řetězec zakódovat jako číslo a rozhodovací problém pak je podmnožina přirozených čísel. Speciálně, řetězec může být „zdroják“ algoritmu v nějakém výpočetním modelu.

Převoditelnost a úplné problémy

Rozhodovací problémy lze uspořádat pomocí (různých druhů) převoditelnosti. Rozhodovací problém se nazývá úplný pro nějakou množinu problémů, pokud patří do této množiny a na něj jdou převést všechny problémy z této množiny. +more Neformálně, úplný problém je nejtěžší problém z dané třídy, například pro třídu NP je to problém SAT nebo kterýkoli NP úplný problém.

Rozhodovací problémy při převoditelnosti nepotřebují převádět výsledek zpět jako obecné výpočetní problémy. Lze požadovat, aby odpovědi pro převáděnou i převedenou instanci byly stejné, tj. +more obě ANO nebo obě NE (případně obě divergují). To zjednodušuje konstrukce a důkazy.

Jiné formulace problémů

V praxi

Rozhodovací problém SAT, splnitelnosti výrokové formule (často zadané v CNF), se používá ve verifikaci programů a verifikaci obvodů. Metody řešení čistě boolovských formulí jsou založeny na algoritmu DPLL. +more Konjunkce formulí v lineární reálné nebo racionální aritmetice jsou řešitelné simplexovým algoritmem, další rozhodnutelné teorie mají svoje specializované algoritmy. Pro obecnější formule a kombinování metod se používá řešení SMT (Satisfiability Modulo Theories).

Kategorie:Vyčíslitelnost