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 L₁ nyelved, és el akrod dönteni, hogy $x\in L_1$-e és van Karp redukciód egy L₂ 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 L₂-ben működő algoritmusokkal meg tudod oldani az L₁-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 tanu-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 bármelyik másik NP-beli nyelvet is el tudjuk 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, #-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 RH₁ a részhalmaz-összeg probléma azon speciális esetét, melyben az első súly 1 (a tanult jelöléssel: s₁=1). Igazoljuk, hogy az RH₁ 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,2ⁿ)-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.