NP-úplnosť Flashcards
polynomiálny čas je taká vlastnosť problémov, ktorá je …
nezávislá od výberu výpočtového modelu, pokiaľ sa hýbeme v prvej počítačovej triede
Čo je prvá počítačová trieda?
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…
Triedu P rozhodne môžme považovať za triedu …
prakticky riešiteľných úloh
Ako inak vieme opísať triedu NP?
problémy, ktorých riešenie vieme overiť v čase polynomiálnom od veľkosti vstupu
Na čo sú NP-úplné problémy?
pre mnohé problémy pomerne ľahko ukážeme, že sa za predpokladu P != NP v polynomiálnom deterministickom čase riešiť nedajú
Aké sú aproximačné, pravdepodobnostné a heuristické algoritmy?
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
Definuj polynomiálnu redukovateľnosť
str. 26
Definuj NP-úplné problémy
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ý.
Ak prienik NPU a P nie je prázdny, tak
P=NP
Ak P != NP, tak
NPU je podmnožina NP-P
Čo stačí na dôkaz P=NP?
pre jediný NP-úplný problém nájsť deterministický polynomiálny algoritmus.
Aká je alterntívna definícia NPÚ?
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.
Ako vieme dokázať, že je jazyk NP-úplný?
- Dokážeme, že je v NP
- Dokážeme, že je NP-ťažký, pomocou tranzitivity polynomiálnej redukovateľnosti, teda napr. ukážeme, že vieme na neho zredukovať SAT
Čo je boolovská formula?
x, negácia x, spojenie boolovských formúl logickou spojkou
Ako označujeme boolovskú formulu BF s n premennými x1, x2, …, xn?
BF(x1,…,xn)
Kedy je BF(x1,…,xn) splniteľná?
Ak existuje priradenie pravdivostných hodnôt x1,…,xn tak, že formula je pravdivá
Čo je problém splniteľnosti BF?
Na vstupe dostanem BF a výsledok je 1 ak je splniteľná, 0 inak
Vyslov a dokáž Cook-Levinovu vetu
Problém splniteľnosti BF je NP-úplný
Dôkaz na strane 28, je to celkom hard a dlhé
Akých 7 podmienok musí platiť v dôkaze Cook-Levinovej vety?
- Q0 je počiatočná konfigurácia
- V každom čase je hlava na práve jednom políčku
- V každom čase je stroj práve v jednom stave
- V každom čase je na každom políčku pásky práve jeden symbol
- Mení sa len to políčko, na ktorom je nastavená hlava
- Zmena sa deje podľa prechodovej funkcie
- Posledná konfigurácia je akceptujúca
Načrtni iný dôkaz Cook-Levinovej vety
str 32
Dokáž, že 3-SAT je NPÚ
SAT => KNF => 3SAT, konkrétny princíp str, 34
Dokáž, že problém k-kliky je NPÚ (k-klika = úplný podgraf s k vrcholmi)
str. 35, NP-hard idea: redukcia KNF => k-klika
príslušnosť do NP je easy
Dokáž, že problém k-pokrytia (mn. k vrcholov taká, že pre každú hranu aspoň jeden vrchol v tejto mn.) je NPÚ
https://www.geeksforgeeks.org/proof-that-vertex-cover-is-np-complete/
Dokáž, že problém vrcholovej k-zafarbniteľnosti je NPÚ
str. 36
Dokáž, že problém existencie Hamiltonovskej kružnice je NPÚ
str. 38
Aké 3 verzie problému plnenia batoha poznáme?
subset-sum 0/1 batoh
rozhodovací 0/1 batoh
optimalizačný 0/1 batoh
def. str. 39
Dokáž, že problém subset-sum 0/1 batoh je NPÚ
str. 40
Definuj problém kontajnerov
str. 41
Definuj problém rozdelenia
str. 42
Definuj problém riadenia skladu
str. 42
Definuj problém hranového vnárania do mriežky
str. 43
Definuj problém dostatku registrov
str. 43
Definuj problém konštrukcie krížovky
str. 43
Definuj problém minimálnej množiny testov
str. 43
