Zadania

wejście na P I(od i do n) L_;, L - połowa samy wszystkich elementów L=(Z S(n))/2, S(n) - pojemność programu. Za pomocą PROBLEM chcemy rozwiązać PARTITION. Jeżeli się to uda to PaPROBLEM. Zapychamy na max oba dy-sRi, to znaczy, że każdy elemem znalazł się na jakimś dysku => rozwiązałem problem podziału zbioru.

45. Czy Klika a NZW oraz NZW' a Klika ?

Klika a NZW, NZW a Klika, zakładając, że K.lika=NPC. Klika i NZW to właściwie to samo, jeżeli zamiast grafu G weźmiemy jego dopełnienie to jeden problem przechodzi w drugi.

1)    Klika a NZW gra? G-»^t Graf G prógP -V prógP

2)    NZW a Klika graf G -N Grał' G próg P -V próg P

Jeżeli iv grafie G istnieje Klika o rozmiarze co najmniej P (podgraf pełny stopnia p), to po przejściu na dopełnienie G w miejscu kliki powstaje niezależny zbiór wierzchołków NZWeNPC.

46. Indeks chromatyczny liczymy z tzw. A_max(G)^X^ł(G) SA_m„(G)t1, gdzie A_max(G) — mai stopień grafu G> należy policzyć mai stopień wierzchołka i zwrócić Am^l. procedurę i ndexchiom( Aimatrbęn: integer) ńnteger, fcegin

for i:=ł to n do fcegin

stopień:=0;

for j:=0 to n do stopień:=stopisń*A(ij]; if(stopień>A^) then A^^stopień end; end;

47. CNT-SAT a Klika

Q=Cj, C₂,.... Ctj - fortnuia logiczna w CNF, X; - literały. Pokażę jak skonstruować z Q graf G=(V,E) taki, że G cędzie posiadał klikę o rozmiarze co najmniej k jeżeli Q jest możliwe do spełnienia. Jeżeli Q jest długości m, to G można uzyskać w czasie 0(m~). Wynika stąd, że mając wielomianowy algorytm na klikę możemy uzyskać wielomianowy algoiytm dla speinialności. poprzez użycie tej konstrukcji. Dla dowolnego Q graf G jest zdefiniowany jako : V - poetykietowany przez literały, a E jest zdefiniowany jako :

wierzchołki tej samej klauzuli są niezależne,

wierzchołki różnych klauzul są połączone ze sobą. chyba, że ich etykiety są negacjami siebie.

Jeżeli Q może być spełnione, wtedy istnieje zbiór wartości prawd dla każdego X; takich, że każda klauzula jest prawdziwa. Z powodu tego przypisania istnieje conajmniejl litera! w każdym Cj, który czyni, go prawdziwym. Jeżeli Sjest zbiorem takich wierzchołków, 1 wierzchołek na klauzulę, wtedy S z definicji tworzy G, tworzy klikę o rozmiarze k. Podobnie jeżeli G posiada kilkę o rozmiarze co najmniej k, wtedy ma klikę o rozmiarze dokładnie k, ponieważ G nie może mieć kliki o rozmiarze większym niż k. Niech S będzie zbiorem zmiennych przypisanych do wierzchołków takiej k-klild. Ponieważ S nie może zawierać jednocześnie literałów i ich elementów komplementarnych : więc poprzez przypisanie Xi=true jeśli X_;eS i X,-=false jeśli X,eS i wybranie arbitralnie wartości prawd dla zmiennych nie należących do S możemy spełnić wszystkie klauzule w Q, Wniosek - Q jest spelnialne c=> G posiada klikę o rozmiarze co najmniej k.

43. CNT-SPEŁNTALNOŚĆ eNPC

Jest NP, bo podać można medeiermimstyczny algorytm o wielomianowym czasie działania, który kończy się sukcesem jeżeli dane wyrażenie jest spełnione.

Procedurę SAT Bcgjn

for i:=l to n do    O(n)

x,:=choicc(truc, false); if CNF is truć then success 0(:i) dse faiJurc;

end;

Trzeba jeszcze dowieźć, że' inny problem NP może być redukowałny do CNF-SAT.