Resize of

I

Kolokwium ze Złożoności Obliczeniowej Algorytmów

..    • • • • o

5-3 | Niech SPj, SPj, SP₃, SP< i SPj będą następująco sformułowanymi zagadnieniami:

K/PC Problem SPi: dany jest zbiór skończony A_x; funkcja s_x: Aj -f N i liczby naturalne fcj, a_x; czy istnieje zbiór Bi C Aj taki,    *i(6) = a_xfc_x?._;...

P Problem SP₂: dany jest zbiór skończony Aj, funkcja a₂: Aj -f N i liczba naturalna **; czy istnieje zbiór Ba C A₂ taki, że |Ba| = fca i £_ł€Bł'e₂(6) = kj?

KI PC Problem SP3: dany jest zbiór skończony A3, funkcja s₃: A3 -+ N i liczba naturalna Jfc₃; czy istnięjc zbiór B₃ C Aa taki, że £_aeB, *3(6) = 2*₃? • .

N^ Problem SP<: dany jest zbiór skończony A«, funkcja s<: A* -> N i liczba naturalna fc«; czy istnieje zbiór B₄ C A< taki, że EkeB₄ ⁵<(⁶) = W

f Problem SP₆: dany jest zbiór skończony A$, funkcja a_s: As -ł N i liczba naturalna k₅; czy istnieje zbiór B» C As taki, że |B_a| = k₅ i ^_ł€Bł s₅(6) = 2Jks?

Wypełnij poniższe pola, umieszczając w polu o numerze i opis redukcji SPjoSPj+j (jeżeli taka redukcja nie istnieje, napisz "nie istnieje”). Uwaga! Przyjmy, że P / NP.

Ul£ ISTNieJE	3^- ls2-'«(»IŁ %-Uaj Z tri	Au, V"^S3	Mię ISTN/EJC
| 15-10 1 Niech PK(k)	będzie następująco sformułowanym podproblemem problemu komiwojażera: dane jest pomiędzy miastami M = [my] oraz liczba naturalna p, przy czym my € {Jb,k + 1} •zy można przejść przez rozważane miasta w taki sposób, że każde zostanie odwiedzone bytej drogi będzie mniejsza lub równap? Wykaż, że PK(3) jest problemem NP-zupelnym.
n miast, macierz odległości dla każdych 1 < i j < n; dokładnie raz, a długość prze