Resize of+

Kolokwium ze Złożoności Obliczeniowej Algorytmów 1 czerwca 2CC2

|    | 5-3~~j Niech SPi, SP₂, SP₃, SP4 i SP5 będą następująco sformułowanymi zagadnieniami:

p Problem SPj: dany jest zbiór skończony A_łf funkcja «i: Aj -> N i liczba naturalna k\^m, czy istnieje zbiór Bi C Ai taki, że |Bi| = Jy i EieB, = *,?

'JsJPC Problem SP₂: dany jest zbiór skończony A₂, funkcja sr.Ai -* N i liczba naturalna *2; czy istnieje zbiór Bi C A₇ taki, że E*en_a *2(6) = 2*2?

N pC Problem SP₃: dany jest zbiór skończony Aj, funkcja s₃: Aj -ł N i liczby naturalne Jk₃, a₃; czy istnieje zbiór Bz C As taki, że E_5€/Jj s₃(&) = e₃*₃?

M TC Problem SP4: dany jest zbiór skończony A4, funkcja s_t: Aą -> N i liczba naturalna *4; czy istnieje zbiór B4CA4 taki, że E»_€b« *4(6) = *4?

P Problem SP₃: dany jest zbiór skończony Aj, funkcja a$: Aj N i liczba naturalna *5; czy istnieje zbiór BtCAs taki, że |B_S| = *j i Ełefl. •«(*) = 2*5?

Wypełnij poniższe pola, umieszczając w polu o numerze » opis redukcji SP.aSPi+i (jeżeli taka redukcja nie istnięje, napisz "nie istnieje”)- Uwaga! Przyjmij, że P £ NP.

| 15-10~| Niech PK(*) będzie następująco sformułowanym podproblemem problemu komiwojażera: dane jest n miast, macierz odległości pomiędzy miastami M = [my] oraz liczba naturalna p, przy czym my € {*,* + 1} dla każdych 1 < * £ j < n\ czy można przejść przez rozważane miasta w taki sposób, że każde zostanie odwiedzone dokładnie raz, a długość przebytej drogi będzie mniejsza lub równa p? Wykaż, że PK(4) jest problemem NP-zupełnym.

Strona 2