Ha vannak is tippek a megoldáshoz, azok , csak segítségek
amik visszaellenőrzésre/elindulásra alkalmasak.
Feladatsor
A gyakorlat honlapja
Spoiler-free: ki kell jelölni az adott sort, amelyikre kíváncsi vagy
1. UNIO-HOLVAN adatszerkezet
2. def...
3. háromnál hosszabb páratlan kör, plusz egy pont minddel összekötve
4.(a) P-beli (tehát NP és coNP): magyar módszer
4.(b) P-beli (tehát NP és coNP): minden fok páros és öf. gráf
4.(c) MAXFTLEN NP-teljes probléma. Hatékony tanúsítvány: egy $k$ méretű független ponthalmaz
4.(d) RH NP-teljes probléma. Hatékony tanúsítvány: egy ilyen részhalmaz
5. Plusz egy pont minddel összekötve, a=1, b=k.
6. (Partíció) Vegyünk fel egy plusz elemet, amely az eddigiek összegének fele.
7. (3-SZÍN) Vegyünk fel csúcsokat amíg nem teljesül.
8. P-beli, mert max 4 csúcsú klikk lehet benne.
9.(a) H-út: két új pont mindegyikkel összekötve
9.(b) H-út: Ekvivalens
9.(c) H-út: Plusz egy-egy lelógó csúcs mindenhol
9.(d) H: Plusz 99*|V(G)| csúcs
9.(e) H: Plusz |V(G)|^2-|V(G)| csúcs
10. Töröljük S-en belül futó éleket, nézzük meg, hogy öf. marad-e (BFS).
11. Van legfeljebb k levélösszsúlyú feszítőfa G-ben | NP-teljes | Hút visszavezethető erre | Legyen s(v)=1, k=2
12. NP | PARTÍCIÓ általánosítása, tehát az visszavezethető rá | vegyük fel annyiszor az összeg felét új elemként, ahány szinttel több van, mint 2
13. L_1\prec L_2, mert L_1 P-beli és L_2 NP-beli (P részhalmaza NP-nek). Fordítva akkor és csak akkor igaz, ha P=NP.
14. Indirekt | Tfh. coNP=/=NP és MAXKLIKK P-beli. Ekkor, mivel MAXKLIKK NP-teljes, P=NP, tehát NP részhalmaza coNP (mert P is). Tudjuk, hogy bármely L coNP-beli problémára a komplementere NP-beli. Mivel P=NP, L komplementere P-beli, tehát coNP-beli is (a részhalmaz viszony miatt), ami miatt viszont L NP-beli, tehát coNP=NP. Ellentmondás...
15.(a) Nem (ettől még lehet P-beli)
15.(b) Igen (NP-teljes)
15.(c) Nem (P részhalmaza NP-nek).
16. NP-teljes | H | S=V(G)
17. P-beli | csak az a kérdés, hogy az S által feszített részgráfban van-e kör | DFS S-en belül
18. NP-teljes | H | vegyünk fel 4n plusz csúcsot
19. P-beli | Összefüggő marad-e, ha e-t töröljük | BFS G-{e}-ben
20. NP-teljes | 3-SZÍN | vegyünk fel egy 97 csúcsú klikket és kössük össze minden pontját a gráf minden pontjával
21. NP-teljes | 3-SZÍN | vegyünk fel két új csúcsot, y-t és z-t. x-et random választjuk. kössük össze őket
22. P-beli | Vegyük az összes lehetségest, az O(n^{1000})
23. NP-teljes | H | Iktassunk be minden él helyett egy 1000 hosszú utat
24. P-beli | Kétszeres összefüggőség a kérdés | minden e-re BFS G-{e}-ben
25. dinprog | minden s_i-re adjuk meg, hogy 0 és b között mely egészek hozhatók ki, ha s_i-t bevesszük
26.(a) Vegyünk fel egy különálló kört.
26.(b) H NP-teljes, az (a) miatt 2KÖR is az, ha NP-beli. Két kör jó tanúsítvány, tehát létezik NP-beli. Létezik visszavezetés.
27. Indirekt | Tfh. NP=/=coNP | ha A NP-beli, akkor visszavezethető X-re (mert az NP-teljes), ami coNP-beli, tehát A is az, ezért NP részhalmaza coNP-nek. Ugyanez coNP-beli B-vel belátható kihasználva azt, hogy X komplementere coNP-teljes és NP-beli
Ha esetleg ennek az oldalnak szeretne örülni valaki: