Ha vannak is tippek a megoldáshoz, azok , amik segíthetnek, illetve visszaellenőrzésre alkalmasak.
Teszek ide is gombot:
Feladatsor - a feladatok eszerint vannak sorszámozva
Ki kell jelölni a sort, hogy "látsszon".
1. páratlan kör, plusz egy pont minddel összekötve
2. NP-teljes | X3C visszavezethető rá | Legyen r:=A/3.
3. Van legfeljebb k levélösszsúlyú feszítőfa G-ben | NP-teljes | Hút visszavezethető erre | Legyen s(v)=1, k=2
4. NP | PARTÍCIÓ általánosítása, tehát az visszavezethető á | vegyük fel annyiszor az összeg felét új elemként, ahány szinttel több van, mint 2
5. L_1\prec L_2, mert L_1 P-beli és L_2 NP-beli (P részhalmaza NP-nek). Fordítva csak akkor igaz, ha P=NP.
6. Indirekt | Tfh. coNP=/=NP és MAXKLIKK P-beli. Ekkor, mivel MAXKLIKK NP-teljes, P=NP, tehát NP részhalmaza coNP (mert P is). Tudju, 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...
7.(a)Nem (ettől még lehet P-beli)
7.(b)Igen (NP-teljes)
7.(c)Nem ($P\subseteq NP$).
8.NP-teljes | H | ez pont az, nem kell Karp-redukció
9.P-beli | csak az a kérdés, hogy az S által feszített részgráfban van-e kör | BFS
10.NP-teljes | Hamilton | vegyünk fel 4n plusz csúcsot
11.P-beli | Összefüggő marad-e, ha e-t töröljük | BFS G-{e}-ben
12.NP-teljes | 3-SZÍN általánosítása | vegyünk fel csúcsokat, ami minddel össze van kötve
13.NP-teljes | 3-SZÍN általánosítása | vegyünk fel két új csúcsot, y-t és z-t. x-et random választjuk. kössük össze őket
14.P-beli | Vegyük az összes lehetségest, az O(n^{1000}) (n alatt 1000)
15.P-beli | A komplementer gráfban vegyük az összes lehetségest (megvan-e mind), az O(n^{1000}) (1/1000*n*(n-1)*(n-2)*...*(n-999))
16.P-beli | Kétszeres összefüggőség a kérdés | minden e-re BFS G-{e}-ben
ez a honlap kávészínű | C0FFEE