NP-optimalizačné problémy

Question 1

Definuj NP-optimalizačný problém

Answer 1

str 51 (cieľ, pol. ohraničená relácia, hodnotová funkcia)

Question 2

Podľa cieľa aké problémy poznáme?

Answer 2

minimalizačný a maximalizačný

Question 3

Definuj konštrukčný problém

Answer 3

Pre dané x nájdi ak existuje y také, že (x,y) v R a hodnota m(x,y) je minimálna/maximálna

Question 4

Definuj hodnotový problém

Answer 4

Pre dané x urči ak existuje minimálnu/maximálnu hodnotu m(x,y) (teda pre všetky y to prejsť)

Question 5

Definuj rozhodovací problém

Answer 5

Pre dané x a pr. číslo k zisti, či existuje také y, že (x,y) v R a m(x,y)≤k pre cieľ min, podobne m(x,y)≥k pre cieľ max

Question 6

Ako vieme formulovať rozhodovací problém ako jazyk?

Answer 6

str. 52

Question 7

Dokáž, že rozhodovací problém každého NPO patrí do NP

Answer 7

str 52
nedeterministicky uhádneme y a dopočítame (idea)

Question 8

Dokáž vetu 6.2 na str. 52 o konštrukcii rozhodovacieho problému na konštrukčný

Answer 8

str. 52

Question 9

Ak P=NP, potom konštrukčný problém každého NPO možno …

Answer 9

riešiť deterministicky v polynomiálnom čase

Question 10

Dokáž dôsledok 6.3

Answer 10

str. 53

Question 11

Formalizuj problém konštrukcie hamiltonovskej kružnice grafu x

Answer 11

str. 54

Question 12

Definuj čo je m*(x)

Answer 12

optimálna hodnota min/max pre dané x

Question 13

Definuj alfa-aproximovateľný NPO

Answer 13

str. 54

Question 14

Definuj dobre aproximovateľný problém

Answer 14

ak je alfa-aproximovateľný pre každé alfa > 1 (limitne sa blíži 1)

Question 15

Definuj neaproximovateľný problém

Answer 15

Ak nie je alfa-aproximovateľný pre žiadne alfa > 1

Question 16

Dokáž a vyslov vetu 6.5 o P!=NP a existencii NPO problémov A,B,C

Answer 16

str. 54

Question 17

Dokáž: Ak P!=NP, potom NPO problém obch. cestujúceho je neaproximovateľný

Answer 17

str. 56

Question 18

Za predpokladu P!=NP, aké ďalšie problémy sú neaproximovateľné/aproximovateľné?

Answer 18

str. 57

Question 19

Definuj NPO 0/1 batoh

Answer 19

str. 57

Question 20

Definuj konštrukčný 0/1 batoh

Answer 20

str. 57

Question 21

Definuj rozhodovací 0/1 batoh

Answer 21

str. 58

Question 22

Opíš riešenie konštrukčného 0/1 batoha, aj s algoritmom. Aká je jeho časová zložitosť?

Answer 22

str. 58

Question 23

Opíš aproximačný algoritmus pre konštrukčný 0/1 problém batoha

Answer 23

str. 59

Question 24

Doplň: NPO 0/1 problém batoha je …

Answer 24

dobre aproximovateľný

Question 25

Čo sú pseudopolynomiálne algoritmy? (neformálne)

Answer 25

str. 61

Question 26

Definuj Num, Int, MaxInt

Answer 26

str. 61

Question 27

Definuj pseudopolynomiálny algoritmus

Answer 27

str. 61 Ak pre jeho zložitosť T() platí T(x)=O(p(|x|,MaxInt(x))) Teda je polynomiálny pre celočíselné vstupy, ktoré sú zadávané unárne

Question 28

Kedy je pseudopolynomiálny algoritmus efektívny?

Answer 28

Keď maximálna hodnota na vstupe je rozumná a ohraničená rozumnou funkciou

Question 29

Definuj h-zúženie

Answer 29

str. 61

Question 30

Dokáž a vyslov vetu 6.10 o h-zúžení

Answer 30

str. 62

Question 31

Definuj silno NP-hard problém

Answer 31

Problém U je silno NP-hard ak existuje polynóm p taký, že p-zúženie U je NP-ťažký problém

Question 32

Dokáž vetu: Nech P!=NP, U je silno NP-hard s celočíselnými vstupmi. Potom neexistuje alg. pseudopolynomiálnej zložitosti riešiaci U

Answer 32

str. 62

Question 33

Čo nám teda stačí ukázať, ak chceme vyargumentovať, že nejaký celočíselný problém je veľmi ťažký?

Answer 33

Že pre neho neexistuje pseudopolynomiálny algoritmus.

Question 34

Ako konkrétne vieme ukázať, že neexistuje pseudopolynomiálny algoritmus?

Answer 34

Pre nejaký polynóm h je h-zúženie U NP-hard. Dôkaz robíme tak, že naň zredukujeme nejaký NPÚ alebo NP-hard problém.

Question 35

Definuj TSP (travelling salesman) ako vstup/výstup a dokáž, že je NP-hard

Answer 35

Dôkaz: pomocou redukcie HAM na TSP