Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Prakticky riešiteľné problémy jl Kritérium efektivity HNP-úplné problémy Redukcia iĎalšie zložitostné tr IB110 Podzim 2010 1 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Praktická použiteľnosť algoritmov Je každý algoritmus prakticky použiteľný? N = 1 000 000 e O(log N)... 20 e O(N)... 1 000 000 triedenie žožnamu O(N log N)... 20 000 000 Hanojské veže O(2N)... milión presunov ža minUtu => 500 000 rokov Je rieSením výkonnejší hardware a väCSia trpežlivost? IB110 Podzim 2010 2 Prakticky riešiteľne problemy^Kritérium efektivity ^ ^ Monkey Puzzle Problem http://www.keithharingart.com/ IBllO Podzim 2010 3 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ MP hlavolam Vstup N kariet (N = M2) a DajU sa karty usporiadal! do Štvorca M x M tak, aby sa susediace hrany zhodovali? Karty majú fixnú orientáciu (nemôžeme ich otáCat) Zaujíma nas len existencia riesenia (nepotrebujeme poznat! usporiadanie vyhovujuce podmienkam) IB110 Podzim 2010 4 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ MP hlavolam - riešenie ■ je daný konečný počet kariet ■ každú kartu možeme umiestnitna konečný počet pozícií ■ môžeme výskúSat vSetký možnosti ■ N = 25 x 25, počet možností 25 x 24 -x 3 x 2 x 1 ■ 109 možností ža sekundu => 490 miliónov rokov IB110 Podzim 2010 5 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Hranice praktickej použiteľnosti v 20 60 100 300 1000 5N 100 300 500 1500 5000 N x log2(V 86 354 665 2469 9966 M2 400 3600 10.000 90,000 1 million (7 digits) W3 8000 216.000 1 million (7 digits) 27 million (8 digits) 1 billion (10 digits) 2N 1.048.576 a 19-digit number a 31-digit number a 91-digit number a 302-digit number Ml a 19-digit number an 82-digit number a 161-digit number a 623-digit number unimaginably large NN a 27-digit number a 107-digit number a 201-digit number a 744-digit number unimaginably large IB110 Podzim 2010 6 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Hranice praktickej použiteľnosti 20 40 60 100 300 N2 1/2500 millisecond 1/625 millisecond 1/278 millisecond 1/100 millisecond millisecond N5 1/300 second second 78/100 second 10 seconds 40.5 minutes 2N 1/1000 second 18.3 mi tm tes 36.5 years 400 billion centuries a 72-digit number of centuries NN 3.3 billion years a 46-digit number of centuries an 89-digit number of centuries a 182-digit number of centuries a 725-digit number of centuries hranica: polynomialna zložitosť prakticky rieSitel'ne vs prakticky nerieSitelne problémy IB110 Podzim 2010 8 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Prakticky neriešiteľné problémy i použil! výkonnejší počítač? pre algoritmus zložitosti 2N: ak dnes vyriešime inštancie velkosti max. C, tak 1000 krát rýchlejším počítačom vyriešime inštancie velkosti max. C + 9.97. ■ zintenzívnit! výžkum a najst efektívnejší algoritmus? ■ dokažat, že neexistuje efektívnejší algoritmus? Millenium Prize Problem, 1 000 000 http://www.claymath.org/millennium/ ■ je otažka doležita? existují aj iná (doleZite) problémy podobného charakteru? IB110 Podzim 2010 9 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ Prakticky riešiteľné problémy Kr NP-úplné problémy ■ Redukcia IB110 Podzim 2010 10 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ NP-Uplne problémy NP-uplne problemy problemy, pre ktore maju linearny dolný odhad žložitosti a exponencialny horný odhad žložitosti nepoznáme lepší neZ exponenciálny algoritmus a zároveň nevieme dokázat, Ci existuje alebo neexistuje asymptoticky efektívnejší algoritmus IB110 Podzim 2010 11 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ NP-úplne problémy - príklady dvojrožmerne pokrýtie daných je N stvoruholníkov; je možne pokrýt nimi stvorcovú plochu? Hamiltonovska cesta daný je neorientovaný graf; existuje v grafe cesta, ktora navstívi každý vrchol prave jeden krat? obchodný cestujúci daný je neorientovaný graf s ohodnotenými hranami a konstanta K; existuje v grafe Hamiltonovský cýklus dlžký nanajvýs K? u daných je M miestností a N prednasok, každa prednaska ma urcený žaciatok a koniec; je možne roždelit predníský do daných miestností? t! dana je logicka formula; existuje priradenie hodôt jej premenníým, pre ktoríe je formula splnenaí? ... a tisíce d'alsích IB110 Podzim 2010 12 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ NP-úplné problémy - spoloCna charakteristika ■ rozhodovacie probiemy (odpoveď je „Ano" alebo „Nie") m existencia ciastocnych riesení ■ hľadanie riesenia probiemu pomocou zpaatneho vyhl'adavania (backtracking); exponenciálny algoritmus ■ je extremne tazke rozhodnut!, ci reisením vstupnej instancie je „Áno" aelbo „Nie" ■ ak riesením instancie je „Áno", tak je velmi jednoduche dokazat to — pomocou tzv. certifikatu ■ obvykle je certifikat kratky ret!azec (linearny voci N) a jeho overenie je mozne v polynomialnom case IB110 Podzim 2010 13 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ Alternatívna charakterizácia NP-úplných problémov ■ predpokladajme, že mame magickU micu, ktorU budeme používal! pri zpätnom vyhl'adavaní (backtrackovaní) rieSenia inStancie ■ vždy, ked' sa mame rozhodnut!, ako rozSírit ciastocne rieSenie, rozhodnutie urobíme tak, ze si hodíme mincou i „magicno" — minca vzdy vyberie moznost, ktora vedie k rieseniu „Áno" (samozrejme, len ak existuje) ■ pojem nedeterminizmu ■ pre NP-uplne problemy mame nedeterministicke polynomialne algoritmy ■ NP v nazve NP-uplny je skratka pre pre nedeterministicky polynomialny IB110 Podzim 2010 14 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ Pojem úplnosti bud' vsétky NP-úplné problémy sú prakticky riešiteľné alébo Ziadén z nich nié jé prakticky riéšitél'ny ■ ak pré jédén NP-úplny problém skonštruujémé polynomiúlny algoritmus, tak múmé polynomialné algoritmy pré všétky NP-úplné problúémy ■ ak pré niéktory NP-úplný problém dokúZémé nééxisténciu polynomialného algoritmu, tak polynomialny algoritmus nééxistujé pré Ziadén NP-úplny problém IB110 Podzim 2010 15 Prakticky riešiteľné problémy^NP-Uplné problémy ^ Redukcia ^ Dokáž Úplnosti Polynomialna Casova redukcia Pre dane dva rožhodovacie problemy Pi a P2; polynomialna Casova redukcia je algoritmus A taký, že A ma polynomialnu casovu žložitost a ■ 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í Y je tiež „Áno". IB110 Podzim 2010 16 Prakticky riešiteľné problémy^NP-Uplné problémy ^ Redukcia ^ Polynomialna redukcia - príklad redukcia probiemu Hamiltonovškej češtý na probiem občhodneho ceštujuceho Tranšformacia graf G = (V, H) (inštancia problemu Hamiltonovškej češtý) graf G = (V, H) š ohodnoten ím w : H — N a konštanta K, kde V = V, H = V x V, w (h) = 1 pre všetký hraný h G H, w (h) = 2 pre všetký hraný h G H \ H, a K = | V | + 1 (inštancia problemu občhodneho ceštujuceho) ■ tranšformacia ša da výpočítat v polýnomialnom čaše v G Hamiltonovška češta exištuje vtedý a len vtedý ak riešen ím inštančie (G, w, K) problemu občhodneho češtujučeho je „Áno" IB110 Podzim 2010 17 Prakticky riešiteľné problémy^NP-Uplné problémy ^ Redukcia ^ Polynomialna redukcia a existencia algoritmu Predpokladajme, že mame polýnomiílný algoritmus O pre problem obchodníeho cestujuíceho. Ukažeme, ako ža tohto predpokladu skonstruujeme polýnomiílný algoritmus H pre problem Hamiltonovskej cestý. Algoritmus H ^ vstup G transformuj na (G, w, K) ^ aplikuj O na (G, w, K) ] ak riesením (G, w, K) je „Ano", tak vrat odpoved' „Ano" 3 v opacnom prípade vrít odpoved' „Nie" IB110 Podzim 2010 18 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Polynomiálna reduckia a úplnost: Fakt Všetky NP-úplné problémy sú vzájomne polynomiálně redukovatel'ne ■ ak chceme o probleme R dokázal!, Ze je NP-Uplny, nemusíme ukazoval! redukciu medzi R a vetkúmi ostatnymi NP-úplnymi problemami ■ staCí ukazat polynomiúlnu redukciu problemu R na jeden konkretny NP-uúplnúy problúem ■ redukcia je tranzitívna Cookova veta Problem splniteľnosti je NP-uplny. IB110 Podzim 2010 19 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Polynomiálna redukcia - príklad 2 Redukcia 3-zafarbenia mapy na problém splniteľnosti IB110 Podzim 2010 20 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ P=NP? problém P je trieda prakticky riešiteľných problémov (tj. problémov, pre ktoré existujú polynomialne algoritmy) Fakt P C NP Otvorený problem P = NP ? Dôsledky riešenia problemu. IB110 Podzim 2010 21 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ ČiastoCné rieSenie NP-úplnych problémov i pseudopolynomiúlne algoritmy ■ aproximatívne algoritmy ■ nahodnostne algoritmy ■ kvantove algoritmy ■ geneticke algoritmy IB110 Podzim 2010 22 Prakticky riešiteľné problémy^Ďalšie zložitoštné triedy ^ ^ Prakticky rieSitefné problémy ^Kriterium efektivity HNP-uplne problemy Redukcia ^| Dalsie žložitostne triedy IB110 Podzim 2010 23 Prakticky riešiteľné problémy^Ďalšie zložitoštné triedy ^ ^ ESte ťažSie problemy NP-uplne problemy môzu mat! polynomialne algoritmy ■ existuju problemy, ktore dokazatelne nemôzu mat! efektívnejsie nez exponencialne (prípadne este zlozitejsie) algoritmy Príklady: pravdivost formule v bohatšej logike IB110 Podzim 2010 24 Prakticky riešiteľné problémy^Ďalšie zložitostné triedy ^ ^ Priestorová zložitosť ■ časová zložitosť > priestorová zložitosť ■ polynomialny priestor (PSPACE) ■ PSPACE-úplne problémy IB110 Podzim 2010 25 Prakticky riešiteľné problémy^Ďalšie zložitoštné triedy ^ ^ Teoria vypoCtovej žložitosti ■ pojem žložitostnej triedy ■ vžtahy medži žložitostnými triedami ■ LOGTIME C LOGSPACEC PTIME C PSPACE C EXPTIME C EXPSPÁCE ... ■ analogicky pre nedeterminižmus ■ kl'ócovó otóžka presneho vžtahu P C NP C PSPACE IB110 Podzim 2010 26