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 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?)

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,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?

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 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?)

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,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?