[ Pobierz całość w formacie PDF ]
Zadanie 5.17 Udowodnij, że jeżeli L d"p K oraz L jest N P trudny, to K jest N P trudny.
Definicja 5.18 Powiemy, że język K jest N P zupełny, jeżeli jest N P trudny oraz sam
należy do N P.
Lemat 5.19 Jeżeli L jest N P zupełny oraz L " P, to P = N P.
Dowód. Niech K będzie dowolnym językiem z klasy N P. Z definicji zupełności mamy
K d"p L. Ale L " P, więc na podstawie lematu 5.14 mamy K " P. W ten sposób
udowodniliÅ›my zawieranie N P ‚" P. Zawieranie P ‚" N P jest trywialne.
124 Rozdział 5. Czasowa złożoność obliczeniowa
Twierdzenie 5.20 Język SAT jest N P zupełny.
Dowód. Wyżej udowodniliśmy, że SAT " N P. Teraz musimy udowodnić, że dowol-
ny język L " N P redukuje się do SAT. Niech M będzie niedeterministyczną maszyną
Turinga akceptującą L i niech p będzie wielomianem ograniczającym czas maszyny M.
Opiszemy teraz funkcję f redukującą język L do SAT . Słowu wejściowemu w funkcja
f przypisuje wartość f(w), która będzie formułą boolowską. Formuła ta będzie opisywać
obliczenie akceptujące i będzie spełnialna wtedy i tylko wtedy, gdy takie akceptujące obli-
czenie istnieje. Przyjmijmy, że M = (Q, £, “, q0, ´, F ) ma tylko jednÄ… taÅ›mÄ™. Jeżeli sÅ‚owo
wejściowe w długości n należy do L, to istnieje obliczenie akceptujące maszyny M na
słowie w
²0 ’! ²1 ’! · · · ’! ²p(n).
Zakładamy, że
" obliczenie ma dokładnie długość p(n) + 1; Po prostu ostatnia akceptująca konfigu-
racja jest powtarzana potrzebnÄ… liczbÄ™ razy,
" jeżeli w i-tej konfiguracji maszyna w stanie q obserwuje symbol g w j-tej komórce,
to j-ty symbol ²i jest postaci (q, g, m), gdzie m jest numerem instrukcji funkcji
przejÅ›cia zastosowanej przy przejÅ›ciu do ²i+1. MówiÄ…c inaczej pozycja gÅ‚owicy,
stan maszyny oraz numer instrukcji, którą zastosowano do przejścia do następnej
konfiguracji, są dołączone do symbolu na taśmie,
" każda konfiguracja ma długość p(n) + 1 oraz zaczyna się i kończy specjalnym sym-
bolem #,
" “ jest alfabetem roboczym uwzglÄ™dniajÄ…cym dodatkowe symbole na obserwowanej
komórce.
Zmiennymi formuÅ‚y sÄ… Pi,j,g dla każdego 0 d" i, j d" p(n) i 1 d" g d" |“|. Wartość Pi,j,g =
true oznacza, że w konfiguracji ²i na j-tej pozycji stoi symbol g. FormuÅ‚a f(w) bÄ™dzie tak
zbudowana, aby spełniały ją dokładnie te podstawienia, które opisują akceptujące oblicze-
nie maszyny M na słowie w. Formuła f(w) jest koniunkcją następujących podformuł:
" dla każdych i, j
Pi,j,g
1d"gd"|“|
co oznacza, że przynajmniej jeden symbol g " “ jest zapisany na pozycji j w kon-
figuracji ²i,
5.7. Problemy N P zupełne 125
" dla każdych i, j
¬( Pi,j,g '" Pi,j,h)
g =h
w konfiguracji ²i co najwyżej jedna symbol jest zapisany na pozycji j,
" dla każdego i Pi,0,# '" Pi,p(n),#,
czyli na poczÄ…tku i na koÅ„cu konfiguracji ²i sÄ… symbole #,
" P0,1,X (". . .("P0,1,X , gdzie symbole X1, . . . Xk składają się z pierwszej litery słowa
1 k
wejściowego w1, stanu q0 oraz numerów tych instrukcji, które mogą być zastosowa-
ne do stanu q0 i litery w1,
" P0,j,w dla każdego 2 d" j d" n
j
czyli w komórkach od 2 do n mamy resztę słowa wejściowego.
" P0,j,B dla każdego n
w pozostaÅ‚ych komórkach na taÅ›mie w konfiguracji poczÄ…tkowej ²0 mamy symbol
blank B,
" Pp(n),1,F ,
w ostatniej konfiguracji ²p(n) mamy stan akceptujÄ…cy, zakÅ‚adamy, że F jest jedynym
stanem akceptującym i że maszyna zatrzymuje się z głowicą na pierwszej komórce,
" dla każdego 1 d" i d" p(n) formuÅ‚a ¨i, która wymusza, że konfiguracja ²i jest
osiÄ…galna w jednym kroku z konfiguracji ²i-1. Opiszemy jÄ… niżej.
FormuÅ‚a ¨i pilnuje nastÄ™pstwa konfiguracji. Zauważmy, że j-ty symbol w konfiguracji ²i
zależy tylko od trzech symboli stojących bezpośrednio nad nim, tych o numerach j - 1, j
oraz j + 1. Istnieje funkcja logiczna f(W, X, Y, Z), która przyjmuje wartość T rue, jeżeli
symbol Z może sie pojawić na pozycji j pod warunkiem, że w poprzedniej konfiguracji
symbole W, X, Y stoją na pozycjach j - 1, j, j + 1. Zauważmy, że symbol Z jest jedno-
znacznie określony, ponieważ postanowiliśmy włączyć numer wykonywanej instrukcji do
symbolu zawierającego obserwowaną komórkę.
¨i = f(W, X, Y, Z) '" Pi-1,j-1,W '" Pi-1,j,X '" Pi-1,j+1,Y '" Pi,j,Z
j W,X,Y,Z
Długość formuły jest proporcjonalna do p2(n) i deterministczna maszyna może ją wypisać
mając na wejściu słowo w długości n, w czasie ograniczonym przez pewien wielomian.
126 Rozdział 5. Czasowa złożoność obliczeniowa
5.8 Problem k-SAT
W problemie k-SAT instancje są formułami w koniunkcyjnej postaci normalnej, to znaczy
jest koniunkcją klauzul, a każda klauzula jest alternatywą literałów (zmiennych lub ich
zaprzeczeń). W problemie k-SAT żąda się dodatkowo, aby każda klauzula miała dokładnie
k literałów (niekoniecznie różnych).
Twierdzenie 5.21 Problem 3SAT jest N P- zupełny.
5.9 Pokrycie wierzchołkowe
Niech G = (V, E) bÄ™dzie grafem nieskierowanym. Zbiór S ‚" V nazywamy pokryciem
wierzchołkowym, jeżeli każda krawędz ma przynajmniej jeden wierzchołek w zbiorze S.
Problem pokrycia wierzchołkowego
Wejście: graf nieskierowany G reprezentowany przez listy sąsiedztwa oraz liczba natural-
na k,
Pytanie: czy G posiada pokrycie wierzchołkowe S rozmiaru |S| d" k.
Twierdzenie 5.22 Problem pokrycia wierzchołkowego jest N P zupełny.
Dowód: Aatwo udowodnić, że problem pokrycia wierzchołowego jest w klasie N P. Po-
każemy, że problem 3SAT można zredukować do problemu pokrycia. Niech
F = F1 '" F2 '" · · · '" Fq
bÄ™dzie formuÅ‚Ä… w 3SAT, gdzie Fi = (±i1 (" ±i2 (" ±i3). Konstruujemy graf G(V, E) który
ma wierzchołek ci,j dla każdego 1 d" i d" q oraz 1 d" j d" 3. Krawędzie grafu G wy-
glądają następująco: dla każdego 1 d" i d" q trzy wierzchołki ci1, ci2 i ci3 tworzą rójkąt.
Mamy też krawędzie pomiędzy trójkątami; para (ci,j, ck,l) " E wtedy i tylko wtedy, gdy
±i,j = ¬±k,l. MówiÄ…c inaczej, krawÄ™dzie Å‚Ä…czÄ… dwa literaÅ‚y z różnych klauzul, jeżeli jeden
literał jest zaprzeczeniem drugiego. Graf został tak skonstruowany, że formuła ma podsta-
wienie spełniające wtedy i tylko wtedy, gdy odpowiadający jej graf ma pokrycie rozmiaru
2q. Rzeczywiście, jeżeli istnieje podstawienie spełniające, to dla każdej klauzuli można
wybrać jeden literał, który przy tym podstawieniu będzie spełniony. Jeżeli usuniemy te
literały, to otrzymamy pokrycie rozmiaru 2q. Na odwrót, jeżeli mamy pokrycie rozmiaru
2q, to w każdym trójkącie dwa wierzchołki należą do pokrycia, bo mamy q trójkątów i
2q wierzchołków w pokryciu. Wybierzmy teraz podstawienie, które spełniają te literały,
5.9. Pokrycie wierzchołkowe 127
które nie zostały wybrane do pokrycia. W tym podstawieniu nie może być konfliktu. Po-
nieważ konflikt oznaczałby, że w jednej klauzuli wybraliśmy jakiś literał, a w innym jego
zaprzeczenie, ale to jest niemożliwe, bo takie literały są połączone krawędzią w grafie.
Zadanie 5.23 Udowodnij, że następujące funkcje są obliczalne w czasie wielomianowym:
1. pierwiastek naturalny,
2. funkcja, która liczbie w systemie dziesiętnym przyporządkowuje jej odpowiednik w
postaci dwójkowej,
3. funkcja, która ciągowi przyporządkowuje ciąg posortowany,
4. dodawanie, mnożenie, dzielenie liczb w systemie dwójkowym lub dziesiętnym.
Zadanie 5.24 Udowodnij, że następujące języki (problemy) mogą być zaakceptowane przez
deterministyczne maszyny Turinga w czasie wielomianowym.
1. zbiór grafów kolorowalnych dwoma kolorami,
2. zbiór spójnych grafów nieskierowanych,
3. zbiór grafów, które są drzewami,
4. zbiór grafów, które mają cykl Eulera,
5. zbiór słów zawierających poprawne nawiasy jednego rodzaju,
6. zbiór słów zawierających poprawne nawiasy kilku rodzajów,
7. {p#t | słowo p jest podsłowem t},
[ Pobierz całość w formacie PDF ]