Resize of;

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

|    | 5-3 | Niech SPi, SP2, SP3, SP4 i SP5 będą następująco sformułowanymi zagadnieniami:

MFC Problem SPi: dany jest zbiór skończony Ay, funkcja «i:    -+ N i liczba naturalna fci; czy istnięje zbiór

Bi CAi taki, że    «i(&) = *1? .

P Problem SP2: dany jest zbiór skończony Aj, funkcja s₂: A₂ -► N i liczba naturalna *2; czy istnieje zbiór B2 C Ai taki, że \B₂\ = i E_6€Bj *a(&) =

^ fC Problem SP3: dany jest zbiór skończony Az, funkcja S3: ^ N i liczba naturalna fc₃; czy istnieje zbiór B₃C Az taki, że E_łeB, ^a*(^b) = ²*s?

NKC Problem SP4: dany jest zbiór skończony A«, funkcja A< -łNi liczby naturalne £4, o«; czy istnieje zbiór Bk ę Aa taki, że E_k€Bł «<(&) = 04*4?

P Problem SP5: dany jest zbiór skończony A5, funkcja SziAz -* N i liczba naturalna k$\ czy istnieje zbiór Bi C Az taki, że |B_fi| = i E»_€b. *«(⁶) = ²*«?

Wypełnij poniższe pola, umieszczając w polu o numerze i opis redukcji SP<aSP,-_+ł (jeżeli taka redukcja nie istnieje, napisz "nic istnieje”)- Uwaga! Przyjmij, że V tfV.

| 15-10 | Niech PK(k) 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 e {k,k + 1} dla każdych 1 < * 5^ 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(2) jest problemem NP-zupełnym.

Udowodnij, że dla pewnego e <2 istnieje wielomianowy algorytm c-przybliżony dla problemu PK(2)

Strona 2