Vyčíslitelnost a složitost výpočtů

Metoda redukce


Shrnutí kapitoly

Rozhodovací problém definujeme jako množinu případů, které lze chápat jako otázky s odpovědí ano/ne. Každý případ se musí dát popsat/zakódovat slovem nad nějakou pevně zvolenou abecedou. Problém je potom charakterizován jazykem obsahujícím slova - případy s odpovědí ano. Problém je algoritmicky rozhodnutelný, je-li tento jazyk rekurzívní.

Z výsledků předchozího tématu plyne, že řada problémů je nerozhodnutelných. K důkazu jejich (ne)rozhodnutelnosti není nutno užívat vždy diagonalizační metodu, která může být pracná. Bývá jednodušší použít metodu redukce. Redukce je vlastně zobrazení R jednoho problému do druhého (připomeňme, že problémy jsou množiny případů). Přitom odpověď ano/ne na každý případ x prvního problému musí být shodná jako odpověď na redukovaný případ R(x) druhého problému. Říkáme, že případy x a R(x) jsou ekvivalentní. Potom každý algoritmus rozhodující redukovaný problém vlastně rozhoduje i problém původní.

Studijní materiál

Skripta P. Sosík, Teorie vyčíslitelnosti, kapitola 3.3.

Příklady a problémy

1.    (Problém tisku) Dokažte, že pro danou trojici (M,x,y), kde M je Turingův stroj a x, y jsou slova nad jeho vstupní abecedou, je nerozhodnutelné, zda M se vstupem x vypíše na pásku výstup y. (Ekvivalentní tvrzení: neexistuje testovací algoritmus, který by ověřil, zda testovaný program pro všechny možné vstupy vydá správné výstupy.)

o    Návod: zkuste redukci problému zastavení na náš problém. Začněte s dvojicí (stroj M1, vstup x,) která tvoří případ problému zastavení. Pozměňte stroj M1 tak, aby vznikl stroj M2, který vypíše výstup y na pásku tehdy a jen tehdy, když se M1 zastaví. K tomu musí stroj M2 mít přidány nové stavy a pravidla, pomocí nichž vyjde z koncového stavu stroje M1, smaže obsah pásky, který vytvořil M1, a zapíše na pásku slovo y. Pokud se M1 nezastaví, tak se tím pádem nezastaví ani M2. Popište detaily naznačené konstrukce M2. Můžete předpokládat, že M1 nikdy nezapíše na pásku prázdný symbol.

2.    Dokažte, že pro daný stroj M je nerozhodnutelné, zda M(ϵ)=↘. (Ekvivalentní tvrzení: neexistuje testovací algoritmus, který by zjistil, zda se testovaný program s prázdným vstupem zastaví nebo zacyklí.)

o    Návod: viz sekce Výsledky cvičení  ve skriptech

3.    Dokažte, že pro daný stroj M je nerozhodnutelné, zda L(M) = ∅. (Ekvivalentní tvrzení: neexistuje testovací algoritmus, který by zjistil, zda testovaný program pro všechny vstupy odpoví „NE.")

o    Návod: viz sekce Výsledky cvičení  ve skriptech

4.    Ukažte redukci problému k-nezávislá podmnožina na problém k-klika.

o    Návod: vyjděte z opačné redukce vysvětlené ve skriptech, promyslete, co je případně třeba změnit.

5.    Problém k-vrcholové pokrytí je definován takto: případ je dvojice (G,k), otázka zní - existuje v grafu G množina k vrcholů („vrcholové pokrytí") taková, že každá hrana má alespoň jeden vrchol v této množině? (Tato množina tedy svými vrcholy „pokrývá" všechny hrany grafu.) Sestrojte redukci problému k-vrcholové pokrytí na problém k-nezávislá podmnožina.

o    Návod: všimněte si, že když vezmeme v grafu vrcholy, které nepatří do vrcholového pokrytí, pak tyto vrcholy tvoří určitě nezávislou množinu. Žádná hrana totiž nemůže mít oba své vrcholy v této množině.

6.    Sestrojte redukci problému k-vrcholové pokrytí na problém k-klika.

o    Návod: stačí zkombinovat redukce ze dvou předcházejících příkladů.

Předchozí
Následující