Pótgyakorlat a hetedik gyakorlathoz 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! 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?) 5. Mutassuk meg, hogy a $2-SZIN\in P$! 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? 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? Megoldások