Sziasztok! Ahogyan ígértem, most egy részletesebb, magyaráztokkal telerakott feladatsor következik. Aki csak a feladatsorra kíváncsi, az kattintson ide. Van először is a Karp redukció. Emögött az a filozófia, hogy ha van egy L1 nyelved, és el akarod dönteni, hogy $x\in L_1$-e és van Karp redukciód egy L2 nyelvre, vagyis át tudod fogalmazni a kérdést egy másik problémává mégpedig úgy, hogy annak pont akkor van megoldása, ha az eredetinek és még az is igaz, hogy az átfogalmazás (az f függvény) gyorsan megvan, akkor az L2-ben működő algoritmusokkal meg tudod oldani az L1-beli kérdéseket is. Gyakorlásnak az első feladat: 1. Igazoljuk, hogy a Karp redukció tranzitív, azaz: ha $L_1\prec L_2$ és $L_2\prec L_3$, akkor $L_1\prec L_3$ is fennáll! A következő dolog az NP-teljesség: ez definíció szerint két dolgot jelent: az adott nyelv NP-beli, ezt tipikusan a tanú-tétellel igazoljuk és hogy minden NP-beli nyelvet vissza lehet rá vezetni ( van Karp redukció minden NP-beli nyelvből rá). Vagyis az NP-teljes nyelvek azok a nyelvek, amiket ha el tudunk dönteni, akkor már akármelyik másik NP-beli nyelvet is el tudunk dönteni. Azt gondoljuk, hogy az NP-teljes nyelveket nem lehet megoldani polinom időben, ezért úgy gondolunk rájuk, mint nagyon nehéz problémákra. Szerencsére egy csomó nyelvről megmutatták már, hogy NP-teljes, ezért nekünk elég egy ilyen már bizonyítottan NP-teljes nyelvet visszavezetnünk egy nyelvre, ha azt akarjuk belátni, hogy a nyelv NP-teljes. (Az 1. feladat miatt, meggondolni!) Ismerten NP-teljes nyelvek: SAT, 3-SAT, 3-SZIN, MAXFTLEN, MAXKLIKK, RH, X3C és még ezer másik. Vigyázat! Ezeket tudni kell, hogy melyik rövidítés, illetve probléma mit jelent! A vizsgán direkt kérdés is lehet erre, vagy olyan feladat, amiben szerepelnek ezek a fogalmak. Az alábbi feladatok (2., 3., 4.) tipikus NP-teljeses példák. 2. Igazoljuk, hogy a 4 színnel színezhető irányítatlan gráfok nyelve NP-teljes! 3. Jelölje RH1 a részhalmaz-összeg probléma azon speciális esetét, melyben az első súly 1 (a tanult jelöléssel: s1=1). Igazoljuk, hogy az RH1 nyelv ${\bf NP}$-teljes. (Ajánlás: adjunk meg egy $RH\prec RH_1$ Karp-redukciót.) 4. Igazoljuk, hogy a Hamilton-út probléma NP-teljes! (Van-e G-ben $\mid V(G)\mid -1$ élszámú egyszerű út?) Másik dolog, ami előkerülhet vizsgán is, hogy bizonyítsuk, hogy valami probléma P-beli. Ez annyit jelent csak, hogy adjunk polinomiális algoritmust. (Ez legtöbbször lineáris, vagy négyzetes, max. köbös lesz, de bármilyen polinom jó!) 5. Mutassuk meg, hogy a $2-SZIN\in P$! Előfordulhat az is, hogy kis módosítás a feladat kitűzésében nagy változást eredményez a bonyolultságban, erre példa az alábbi két feladat. 6. Igazoljuk, hogy a következő feladat P-beli: Adott egy G gráf és egy $S \subseteq V(G)$ halmaz. Van-e G-nek olyan feszítőfája, melynek végpontjai (elsőfokú pontjai) között S pontjai mind szerepelnek? 7. Igazoljuk, hogy a következő feladat NP-nehéz: Adott egy G gráf és egy $S \subseteq V(G)$ ponthalmaz. Van-e G-nek olyan feszítőfája, melynek végpontjai pontosan az S pontjai? Még egy feladat, itt igazából abban van a nehézség, hogy ki kell bogozni, hogy mi is a feladat. 8. Jelölje H a következő hipotézist: Az NP-teljes feladatok nem oldhatók meg O(1,2n)-nél kisebb lépésszámú algoritmussal, ahol n az input mérete. Mutassuk meg, hogy ha H igaz, akkor a következő feladat nem lehet NP-teljes: Input: Egy n csúcsú irányítatlan gráf G. Kérdés: Van-e G -ben legalább $\log n$ független pont? Érdemes még tudni, hogy 1. NP-teljes feladatok kis változtatással, vagy korlátozással P-beliek lehetnek 2. Előfordulhat, hogy egy probléma NP-beli, ezért nincs remény egy gyors algoritmusra, de közelítő megoldások már lehetnek. Erről előadáson hallhattok még. Megoldások