NP-úplnosť

Question 1

polynomiálny čas je taká vlastnosť problémov, ktorá je …

Answer 1

nezávislá od výberu výpočtového modelu, pokiaľ sa hýbeme v prvej počítačovej triede

Question 2

Čo je prvá počítačová trieda?

Answer 2

Prvú počítačovú triedu tvoria tie výpočtové modely, ktoré sú polynomiálne ekvivalentné viacpáskovému DTS = RAM, MRAM s logaritmickou cenou, jednopáskový a viacpáskový DTS…

Question 3

Triedu P rozhodne môžme považovať za triedu …

Answer 3

prakticky riešiteľných úloh

Question 4

Ako inak vieme opísať triedu NP?

Answer 4

problémy, ktorých riešenie vieme overiť v čase polynomiálnom od veľkosti vstupu

Question 5

Na čo sú NP-úplné problémy?

Answer 5

pre mnohé problémy pomerne ľahko ukážeme, že sa za predpokladu P != NP v polynomiálnom deterministickom čase riešiť nedajú

Question 6

Aké sú aproximačné, pravdepodobnostné a heuristické algoritmy?

Answer 6

aproximačné - približne optimálne riešenie, rýchle
pravdepodobnostné - rýchle, pravdepodobnosť korektnej odpovede vysoká
heuristické - stratégia, nemusíme dostať korektné riešenie, dokonca žiadne aj keď existuje

Question 7

Definuj polynomiálnu redukovateľnosť

Answer 7

str. 26

Question 8

Definuj NP-úplné problémy

Answer 8

Jazyk L0 sa nazýva NP-ťažký,ak ∀L ∈ N P : L je polynomiálne redukovateľný na L0. Ak navyše L0 ∈ NP tak je jazyk NP-úplný.

Question 9

Ak prienik NPU a P nie je prázdny, tak

Answer 9

P=NP

Question 10

Ak P != NP, tak

Answer 10

NPU je podmnožina NP-P

Question 11

Čo stačí na dôkaz P=NP?

Answer 11

pre jediný NP-úplný problém nájsť deterministický polynomiálny algoritmus.

Question 12

Aká je alterntívna definícia NPÚ?

Answer 12

Problém L0 z N P je N P -úplný, ak z existencie algoritmu polynomiálnej zložitosti T(n) riešiaceho L0 vyplýva existencia algoritmu zložitosti pL(T(n)) pre každý problém L ∈ NP, pričom pL je polynóm, ktorý závisí od L.

Question 13

Ako vieme dokázať, že je jazyk NP-úplný?

Answer 13

1. Dokážeme, že je v NP
2. Dokážeme, že je NP-ťažký, pomocou tranzitivity polynomiálnej redukovateľnosti, teda napr. ukážeme, že vieme na neho zredukovať SAT

Question 14

Čo je boolovská formula?

Answer 14

x, negácia x, spojenie boolovských formúl logickou spojkou

Question 15

Ako označujeme boolovskú formulu BF s n premennými x1, x2, …, xn?

Answer 15

BF(x1,…,xn)

Question 16

Kedy je BF(x1,…,xn) splniteľná?

Answer 16

Ak existuje priradenie pravdivostných hodnôt x1,…,xn tak, že formula je pravdivá

Question 17

Čo je problém splniteľnosti BF?

Answer 17

Na vstupe dostanem BF a výsledok je 1 ak je splniteľná, 0 inak

Question 18

Vyslov a dokáž Cook-Levinovu vetu

Answer 18

Problém splniteľnosti BF je NP-úplný

Dôkaz na strane 28, je to celkom hard a dlhé

Question 19

Akých 7 podmienok musí platiť v dôkaze Cook-Levinovej vety?

Answer 19

1. Q0 je počiatočná konfigurácia
2. V každom čase je hlava na práve jednom políčku
3. V každom čase je stroj práve v jednom stave
4. V každom čase je na každom políčku pásky práve jeden symbol
5. Mení sa len to políčko, na ktorom je nastavená hlava
6. Zmena sa deje podľa prechodovej funkcie
7. Posledná konfigurácia je akceptujúca

Question 20

Načrtni iný dôkaz Cook-Levinovej vety

Answer 20

str 32

Question 21

Dokáž, že 3-SAT je NPÚ

Answer 21

SAT => KNF => 3SAT, konkrétny princíp str, 34

Question 22

Dokáž, že problém k-kliky je NPÚ (k-klika = úplný podgraf s k vrcholmi)

Answer 22

str. 35, NP-hard idea: redukcia KNF => k-klika
príslušnosť do NP je easy

Question 23

Dokáž, že problém k-pokrytia (mn. k vrcholov taká, že pre každú hranu aspoň jeden vrchol v tejto mn.) je NPÚ

Answer 23

https://www.geeksforgeeks.org/proof-that-vertex-cover-is-np-complete/

Question 24

Dokáž, že problém vrcholovej k-zafarbniteľnosti je NPÚ

Answer 24

str. 36

Question 25

Dokáž, že problém existencie Hamiltonovskej kružnice je NPÚ

Answer 25

str. 38

Question 26

Aké 3 verzie problému plnenia batoha poznáme?

Answer 26

subset-sum 0/1 batoh
rozhodovací 0/1 batoh
optimalizačný 0/1 batoh

def. str. 39

Question 27

Dokáž, že problém subset-sum 0/1 batoh je NPÚ

Answer 27

str. 40

Question 28

Definuj problém kontajnerov

Answer 28

str. 41

Question 29

Definuj problém rozdelenia

Answer 29

str. 42

Question 30

Definuj problém riadenia skladu

Answer 30

str. 42

Question 31

Definuj problém hranového vnárania do mriežky

Answer 31

str. 43

Question 32

Definuj problém dostatku registrov

Answer 32

str. 43

Question 33

Definuj problém konštrukcie krížovky

Answer 33

str. 43

Question 34

Definuj problém minimálnej množiny testov

Answer 34

str. 43