Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Nerozhodnutelnost
Nerozhodnuteľné problémy
Metóda diagonalizáciel^^^^^^^^^^^^^H
Čiastočne rozhodnutel'ne problemy a stupne nerozhodnutel'nosti
IB110 Podzim 2010
Nerozhodnutefnosli^Nerozhodnutefne problemy ^ ^
Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on what you can do with the machines themselves, but there are no limits on what you can do with software.    Time Magazin, April 1984
IB110 Podzim 2010
2
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Otázka
existujú algoritmické problémy, ktoré sú prakticky neriešiteľné?
je to len otazka dostatoCne dlheho Casu, výkonneho hardwaru resp. sofistikovaných algoritmov ???
alebo existujú problemy, ktore sý principiýlne neriesitelne ???
IB110 Podzim 2010
3
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Pravidlá
uvažujeme algoritmické problémy (tj. problémy určené svojou množinou vstupných inStancií a požadovaným vžtahom medži vstupom a výstupom)
problemy s nekonečnou množinou vstupných instanci í (v opačnom pr ípade pre problem vždy existuje algoritmus žaloženy na vymenovan í vsetkych vstupov a k n ím pr íslusnych vystupov)
algoritmus = program žapísany v programovacom jažyku vyssej urovne
IB110 Podzim 2010
4
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Príklad - domino
Vstup (konečná) množina T typov dlaždíc s farebnými hranami
a je možne dlaždicami pokryl! ľubovoľne vel'kU plochu tak, aby sa dlaždice vždy dotýkali hranami rovnakej farby?
z každého typu je k dispozícii neobmedzený počet dlaždíc
IB110 Podzim 2010
5
Nerozhodnuteľnost^Nerozhodnuteľne problémy ^ ^
Príklad - domino, inštancia 1
Nerozhodnuteľnost^Nerozhodnuteľne problémy ^ ^
Príklad - domino, inštancia 2
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Nerozhodnutefné problémy
Definícia
Problém, pre ktorý neexistuje žiaden algoritmus, sa nazýva nerozhodnutel'ný (algoritmický nerieSitel'ný).
praktický rieSitel'ne problemý praktický nerieSitelne problemý nerozhodnutel'níe problíemý
IB110 Podzim 2010
8
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Príklad - domino
Fakt
Problém domina je nerozhodnutel'ný i „zdroj" nerozhodnutel'nosti
■ ekvivalencia s problemom pokrytia nekonečnej plochý
■ periodicita rieSenia
■ je dôvodom potencialne nekonečný počet moZností?
■ dominový had a jeho varianty
IB110 Podzim 2010
9
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Príklad - Postov korešpondečný problém (PKP)
p dva zoznamy slov X = (xi,... xn) a Y = (yi,...yn)
a existuje konečna postupnost! indexov taka, Ze spojením prísluSnych slov zoznamu X vznikne rovnake slovo ako spojením príslusnych slov zoznamu Y?
	1	2	3	4	5
X	abb	a	bab	baba	aba
Y	bbab	aa	ab	aa	a
riešením inštancie je „Áno", príkladom postupnosti je 2, 1, 1, 4, 1, 5
	1	2	3	4	5
X	bb	a	bab	baba	aba
Y	bab	aa	ab	aa	a
riešením ištancie je „nie"
IBilO Podzim 2010
10
Nerozhodnuteľnost^Nerozhodnuteľne problémy ^ ^
Príklad - ekvivalencia a verifikácia programov
Ekvivalencia
Vstup dva programovacie jazyky vyssej urovne, ktorých syntax je dana syntaktickym diagramom alebo v BNF
Otazka su mnoZiny syntakticky spravnych programov pre oba jazyky zhodne?
Verifikacia
Vstup popis algoritmickeho problemu a program v programovacom jazyku vyssej urovne
a riesi program dany problem? (tj. odpoved' je „Áno" ak pre kazdý vstupnu instanciu problemu sa vypocet programu zastaví a da spravnu odpoved')
Pre oba problémy závisí nerozhodnute'nost na vol'be programovacieho jazyka resp. na vol'be jazyka pre popis algoritmickeho problímu. Pre bezne jazyku sá oba problámy nerozhodnutel'ná.
IB110 Podzim 2010
11
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Príklad - problém zastavenia
Uvažujme algoritmy A a B s množinou vstupných inštancií N Algoritmus A
while X = 1 do X — X - 2 od return X Algoritmus B while X = 1 do
if X je sude do X — X/2
if X je liche do X — 3X + 1 od return X
Algoritmus A pre sude Čísla neskonCí. O algoritme B nieje žname, Ci skonCí pre vsetky vstupne instancie.
IB110 Podzim 2010
12
Nerozhodnuteľnost^Nerozhodnuteľne problémy ^ ^
Príklad - problém zastavenia
Vstup program R v programovacom jažyku L vyssej urovne a množina vstupnych instanci í programu R
Otažka žastav í sa vypocet R pre každu vstupnu instanciu? Problem žastavenia je nerožhodnutelny.
Notácia: R (x) j označuje, Ze výpočet R na x skončí; symbol R (x) j označuje, ze neskončí.
IB110 Podzim 2010
13
Nerozhodnuteľnost^Nerozhodnuteľné problémy ^ ^
Riceova veta
Rozhodnutel'nost je výnimka, ktorá potvrdzuje pravidlo
Zaujíma nas netriviálna vlastnost! programu, ktorý je
(1) pravdivý pre niektoré a nepravdivý pre ostane programy
(2) nieje viazaný na syntax programu, ale vztahuje sa k problemu, ktorý program riesi.
Riceova veta
Vsetky netriviýlne vlastnosti programov sý nerozhodnutel'ne.
Príklady: je výstupom programu vzdy „Áno"?, zastavý program pre kazdy vstup?
IB110 Podzim 2010 14
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Nerozhodnutelnost
N
2 Metóda diagonalizacie
■ Ciastocne rozhodnutelne problemý a stupne nerozhodnutel'nosti
IB110 Podzim 2010
15
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Dôkaz nerozhodnuté Inosti
Analógia s dôkazom NP-uplnosti
(1) dokazeme nerozhodnutel'nost nejakeho problemu
(2) nerozhodnutel'nost d'alsích problemov dokazujeme metodou redukcie
V prípade nerozhodnutel'nosti pouzijeme redukciu, ktoró nemusí byt polynomialne casovo ohranicena.
IB110 Podzim 2010
16
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Redukcia
Redukcia
Pre dane dva rožhodovacie problemy Pi a P2; redukcia je algoritmus A ktory vstupnu instanciu X problemu Pi transformuje na vstupnu instanciu Y problemu P2 taku, že riesením X je „Áno" vtedy a len vtedy, ak riesením Y je tiež „Áno".
IB110 Podzim 2010
17
NerozhodnuteľnosIľ^Metóda diagonalizócie ^ ^
Redukcia - príklad
redukcia problému zastavenia na problém verifikácie
IB110 Podzim 2010
18
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Redukcia a dôkaz nerozhodnutelnosti
Fakt
Ak P1 sa redukuje P2 a P1 je nerozhodnutelný, tak aj P2 je nerozhodnutelný.
Predpokladajme, ze P2 je rozhodnutelný a ze B je algoritmus, ktorý ho riesi.
Pomocou B skonstruujeme algoritmus pre P1. Konretne, vstupný instanciu X problemu P1 prevedieme pomcou algoritmu redukcie na vstupný instanciu Y problemu P2. Pouzijeme algoritmus B a najdeme riesenie Y. Ak riesením Y je „/Ano" tak riesením X je tiez „/Áno". Ak riesením Y je „Nie" tak riesením X je tiez „Nie". To je ale spor s predpokladom, ze P1 je nerozhodnutelný.
IB110 Podzim 2010
19
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Nerozhodnuté fnost prob I ému zastavenia
Tvrdenie
Neexistuje program v L, ktorí pre l'ubovol'nu dvojicu (R, X) (R je syntakticky spravny program v L a X je symbol retazcov), dó na vystup „Ano" príve ak vypocet R pre vstup X skoncí po konecnom pocte krokov a da na vystup „Nie" v opacnom prípade.
Neexistenciu programu pozadovanych vlastností dokazeme sporom.
IB110 Podzim 2010
20
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Nerozhodnutelnost problému zastavenia
Predpokladajme, ze existuje program pozadovanych vlastnostý, nazvime ho Q.
Skonstruujeme novy program v jazyku L, nazvime ho S, nasledovne:
j\ vstupom programu S je syntakticky spravny program W v jazyku L
^ program S preCýta W a vytvorý kopiu W
^ S aktivuje program Q so vstupom (W, W) (volaným Q ako procedury)
^ vypoCet Q na vstupe (W, W) skonCý (z predpokladu o vlastnostiach Q) a vrati S odpoved' („Áno" alebo „Nie").
] ak Q skona s odpoved'ou „Áno", tak S vstupi do nekonecneho cyklu (jeho vypocet sa nezastaví)
] ak Q skoncý s odpoved'ou „Nie", tak S da na vystup „Áno".
IB110 Podzim 2010
21
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ^
Nerozhodnutelnost problému zastavenia - spor
Z konstruckie programu S je žrejme, že S sa pre každy vstup W žastaví (s odpoved'ou „/Áno") alebo jeho vypocet cyklí donekonecna.
Uvažme vypocet S na vstupe W = S. S aktivuje program Q na vstupe (S, S) (bod 3). Podl'a predpokladu Q žastaví. Su dve možnosti:
| Q skoncí s odpoved'ou „/Áno" (tj. áno, program S sa na vstupe S žastaví); v takomto prípade ale S vstípi do nekonecneho cyklu. Dostívame spor.
| Q skoncí s odpoved'ou „Nie" (tj. nie, program S sa na vstupe S nežastaví); v takomto prípade ale S da odpved' „/Áno". Opát dostaívame spor.
IB110 Podzim 2010
22
Nerozhodnuteľnost;S=-Metóda diagonalizácie ^ ^
Metoda diagonalizácie
Georg Cantor
obecna metoda, postavena na princípe rozdielných kardinalít
dokaz, že realných císel je viac ako racionalných; dolne odhadý zložitosti problemov, ...
IB110 Podzim 2010
23
Nerozhodnuteľnost^Metoda diagonalizácie ^Čiastočne rozhodnutelná problemy a stupne nerozhodnuteľnosti ^
KoneCne certifikaty pre nerozhodnutefne problémy
Ánalýgia s NP-uplnymi problemami. V prípade nerozhodnuteľnych problemov pozadujeme od certifikýtov len konecnost a existenciu algoritmu ktory overí, ci daný retazec je certifikýtom.
p certifikatom odpovede „/Áno" je konkretna, konecný postupnosl! indexov; l'ahko overíme, ci daný postupnost indexov mý pozadovaný vlastnost!
certifikatom je samotny konecný vypocet; jednoducho overýme, ci dana postupnosl! krokov je korektnym výpoctom programu na vstupe.
o certifikýtom je postupnosl! dlazdýc a sposob ich skladania
certikat existuje pre odpoved' nie. Certifikatom je konecna plocha E. Pretoze E je konecny a pocet typov dlazdýc je tiez konecny, dokazeme overil', ze E sa neda pokryt' (preveríme vsetky moznosti).
IB110 Podzim 2010
24
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^Čiastočne rozhodnuteľné problémy a stupne nerozhodnuteľnosti ^
Čiastočne rozhodnuteľné problémy
Vsetky predchadzajuce problemy mali certifikat přejeden typ odpovede; hovoríme o tzv. jednosmernom cerfikate.
Definícia
Nerozhodnutel'ne problemy, ktore maju jednosmerny certifikat, sa nazyvaju ciastocne rozhodnutel'ne.
Ciastocne rozhodnutel'ne problemy maju algoritmus, ktory je korektny pre jeden typ vstupných instancií (tj. bud' pre vstupy s odpoved'ou „Áno", alebo pre vstupy s odpoved'ou „Nie"). Algoritmus systematicky overuje vsetky konecne retazce, ci su certifikatom daneho vstupu.
IB110 Podzim 2010
25
Nerozhodnuteľnost;S=-Metóda diagonalizacie ^Čiastočne rozhodnutelné problemy a stupne nerozhodnuteľnosti ^
Dvojsmerné certifikaty
môže nastal! situacia, ked' pre dany problem mame certifikat ako pre odpoved' „Áno", tak aj (iny) certifikat pre odpoved' „Nie" (hovoríme o tžv. dvojcestnom certifikate)?
príklad: problem Hamiltonovskeho cyklu. Certifikatom pre „Áno" vstup je permutacia vcholov (jednoducho overíme, ci tvorí Hamiltonovsky cyklus). Certifikatom pre „Nie" vstup su vsetky permutacie vrcholov (jednoducho overíme, že žiadna permutacia netvorí Hamiltonovsky cyklus).
Fakt
Ák problem ma dvojcestny certifikat, tak je rožhodnutel'ny.
Algoritmus systematicky a striedavo overuje vsetky konecne retažce ci su certifikatom pre dany vstup. Konecnost je žarucena, pretože každy vstup ma svoj certifikat.
IB110 Podzim 2010
26
Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ ČiastoCne rozhodnutelná problemy a stupne nerozhodnutel'nosti ^
ESte tazsie prob I emy?
■ vsetky ciastocne rozhodnutelne problemy su vzajomne redukovatelne (analógia s NP-úplnými problémami, tkroé sú polynomiálně ekvivalentné)
■ existují problemy, ktore sí tazsie nez NP-íplne; platí analígia aj pre ciastocne rozhodnutelne problemy?
problem verifikacie existuje redukcia problemu zastavenia na problem verifikície; opacna redukcia ???
íplny problem zastavenia (je vypocet programu konecny pre vsetky
vstupne instancie?) Existuje redukcia problemu zastavenia na uplny problem zastavenia; opacní redukcia ???
Problem verifikacie ani uplny problem zastavenia nemaju certifikaty
IB110 Podzim 2010
27
Nerozhodnuteľnost^Metoda diagonalizácie ^ ČiastoCne rozhodnutelná problemy a stupne nerozhodnuteľnosti ^
Stupne nerozhodnuteľnosti
analogický ako rozhodnutelne problemý mozeme zoskupil! do rozných zlozitostných tried, tak aj nerozhodnutelne problemý tvoria úrovne podl'a stupňa nerozhodnuteľnosti
kazdú úroven obsahuje problemý, ktore su este ťazsie nez problemý predchíadzajuícej uírovne
prvíe dve uírovne hierarchie tvoria ňciastoňcne rozhodnutel'níe a nerozhodnutel'níe problíemý
d'alňsie uírovne oznaňcujeme suíhrnne ako výsoko nerozhodnutel'níe problíemý
IB110 Podzim 2010
28
Nerozhodnuteľnost^Metoda diagonalizócie ^ ČiastoCne rozhodnutelná problemy a stupne nerozhodnuteľnosti ^
Vysoko nerozhodnuteme problémy - príklad
modifikacia problemu domina kde pozadujeme, abý v nekonecnom pokrýtí bola vopred specifikovana dlazdica pouzita nekonecne vel'a krat
IB110 Podzim 2010
29