Zadania 7

b)    faktory-znoja jest problemem klasy NP., a więc niewielomianowyjn.

c)    faktoryzacja jest w istocie problemem łatwym, bo może być wykonywana w czasie subliniowym 0(sqrt(n)),

d)    badanie, czy liczba jest pierwsza jest trudne obliczeniowo;

e)    faktoryzacja liczb naturalnych jest problemem NPC-

a)    dzielenie jest łatwe obliczeniowo.

b)    nieprawda, gdyż NP. oznacza ni edetermmi styczny wielomianowy - nendeterministie polynomial,

c)    nieprawda - faktoryzacja jest problemem otwartym (NPI), a więc nawet jeśli znajdziemy podzielnik w czasie wielomianowym nie potrafimy tego powtórzyć deterministycznie,

d)    tak szczególnie dla dużych n,

e)    nieprawda, gdyż jest ona problemem KPI.

21. Dany jest zbiór Z liczb naturalnych mocy n>2 i liczba naturalna k. Rozważ złożoność dwóch podobnie brzmiących problemów decyzyjnych :

a)    czy można Z podzielić na dwa aiepuste podzbiory Z1 i Z2 w talu sposób, że sumy liczb w Z1 i Z2 różnią się o więcej niż k ?

b)    czy można Z podzielić na dwa niepuste podzbiory Z1 i Z2 w taki sposób, że sumy liczb w Zl i Z2 różnią się o mniej niż k ?

Problem a) jest problemem łatwym (rozwiązywalnym wielomianowo). Wystarczy do Zl przypisać najmniejszy element ze zbioru Z. a do Z2 pozostałe elementy i sprawdzić, czy różnica między sumą elementów' w* Z2 i Zl jest >k. Problem b) jest problemem NPC, ponieważ można go sprowadzić do problemu podziału zbioru dla k=l.

22. Następujący algorytm rozwiązuje problem Suma Podzbioru dla n-e!ementowego zbioru A i limitu k. Uzasadnij dlaczego algorytm ten nie jest dowodem na to, że P=NP. procedurę Suma?odzbioru(A,n,k); begin

S:-l;

for i:=I to n do

S:=3 or Shift(S»A[i]);    [ funkcja Shift przesuwa bity

if k-ty bit w S=1 then write(“tak”) w słowie o A[ij pozycji w lewo) else writefżaieO;

end:

Ten algorytm nie jest dowodem na to. że P=NP._r gdyż nie posiada on złożoności wielomianowej. Jego złożoność jest iRsuma wartości wszystkich liczb na wejściu. Suma tych wartości jest to suma w szystkich liczb w wektorze A, czyli może być MAX. Algorytm posiada złożoność pseudowielomianową n*max - w max tkwi niewielomianowość.

(

A - ciąg elementu, n - ilość tych elementów, k - obliczona suma, np. 3 elementy' [1,3,3]

S=l:    00000001

a[lj=l    00000001->00000001 o 00000010 = 000000 i 1

a[2]=3    00000011-*000000 Hu 0001 i000 - 00011011

a[3 }=3    OOOlłOll^COOłlOllw 110UC00 = 11011011

CKn^shifi)

Shift=(2^k'"')_ł n - ilość bitów' do zapisu F(n,k)=n*2¹' - wykładniczy w funkcji k.

23. Udowodnij, że nie istnieje algorytm 2-ablsolutnie przybliżony dla problemu Suma Podzbioru, chyba że P=NP. Zai. ? nie jest równe NP, oraz istnieje taki algorytm 2-absolutnie przybliżony ;F.;(.I)-F_A([)!^2.

Rozważę zagadnienie nieco ogólniej: Zakładam, że ismieje aigoryim X-absoIutnie przybliżony dla podanego problemy, gdzie X jest dowolnie duże. Pokaże, że na bazie tego algorytmu można zbudować aigoryim X/2-absoI utnie przybliżony. Mamy zbiór A={al,a2,...,an} i sunie S. Rozwiązanie optymalne wynosi F₀(I)-0. Działam w ten sposób: mnożę wszystkie elementy- przez 2 i podwajam także sumę. Mam wiec A’=(2al,2a2,...,2an}. Działanie to nie zmienia proporcji miedzy elementami, a także między elementami a sumą, stąd me wpływa to jakościowo na wy nik Rozwiązanie optymalne wynosi teraz 20. Do Lek spreparowanych danych stosuje algorytm X-absolutnie przybliżony. Uzyskuję wypełnienie zbioru suma. którą oznaczę przez 2P. Zachodzi przy tym (*) (20-2Pj<X. Teraz dzielę wszystkie wybrane elementy przez 2 i otrzymuję pewien podzbiór zbioru A gdzie suma elementów tego podzbioru z oczywistych względów wy nosi 2P/2=R Dla zbioru A optymalne wypełnienie wynosi O, stąd błąd. jaki popełniliśmy to jO - Pi.

Dzieląc obustronnie równanie {*) przez 2 otrzymuję zależność: JO - P;<X/2. C.N.U.    .