Złożoność obliczeniowa/Test 5: Problemy NP-zupełne: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 1: Linia 1:
<quiz>NP-zupełność problemu 3SAT
+
<quiz>
 
W przedstawionym dowodzie NP-zupełności problemu 3SAT  
 
W przedstawionym dowodzie NP-zupełności problemu 3SAT  
 
<rightoption>klauzula <math>k</math>-składnikowa zastępowana jest przez <math>k-2</math> klauzul</rightoption>
 
<rightoption>klauzula <math>k</math>-składnikowa zastępowana jest przez <math>k-2</math> klauzul</rightoption>
Linia 9: Linia 9:
  
  
<quiz>NP-zupełność problemu MAX2SAT
+
<quiz>
 
Przedstawiona redukcja dowodząca, że MAX2SAT jest problemem NP-zupełnym, jest redukcją logarytmiczną, gdyż  
 
Przedstawiona redukcja dowodząca, że MAX2SAT jest problemem NP-zupełnym, jest redukcją logarytmiczną, gdyż  
 
<wrongoption>działa w czasie wielomianowym</wrongoption>
 
<wrongoption>działa w czasie wielomianowym</wrongoption>
Linia 18: Linia 18:
  
  
<quiz>Dowód NP-zupełności problemu pokrycia wierzchołowego
+
<quiz>
 
Na wejściu redukcji dowodzącej, że problem NODE COVER jest NP-zupełny, dana jest formuła o <math>m</math> klauzulach nad <math>n</math> zmiennymi. W utworzonym grafie jest  
 
Na wejściu redukcji dowodzącej, że problem NODE COVER jest NP-zupełny, dana jest formuła o <math>m</math> klauzulach nad <math>n</math> zmiennymi. W utworzonym grafie jest  
 
<rightoption><math>3m</math> wierzchołków</rightoption>
 
<rightoption><math>3m</math> wierzchołków</rightoption>
Linia 28: Linia 28:
  
  
<quiz>NP-zupełność problemu cyklu Hamiltona
+
<quiz>
 
W jaki sposób w dowodzie NP-zupełności problemu HAMILONIAN CYCLE korzysta się z tego, że gadżet można trawersować dwukrotnie, za każdym razem inną połowę gadżetu?  
 
W jaki sposób w dowodzie NP-zupełności problemu HAMILONIAN CYCLE korzysta się z tego, że gadżet można trawersować dwukrotnie, za każdym razem inną połowę gadżetu?  
 
<wrongoption>Konstruując pokrycie, możemy wykorzystać dwukrotne trawersowanie gadżetu</wrongoption>
 
<wrongoption>Konstruując pokrycie, możemy wykorzystać dwukrotne trawersowanie gadżetu</wrongoption>
Linia 37: Linia 37:
  
  
<quiz>Ścieżka Hamiltona
+
<quiz>
 
Problem HAMILTONIAN PATH, należący do klasy NP,  
 
Problem HAMILTONIAN PATH, należący do klasy NP,  
 
<wrongoption>jest zacieśnienieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny</wrongoption>
 
<wrongoption>jest zacieśnienieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny</wrongoption>
Linia 46: Linia 46:
  
  
<quiz>Trójdzielne skojarzenie
+
<quiz>
 
Jeśli na wejściu redukcji z problemu 3SAT do TRIPARTITE MATCHING dana jest formuła składająca się z <math>m</math> klauzul nad <math>n</math> zmiennymi, to na wyjściu  
 
Jeśli na wejściu redukcji z problemu 3SAT do TRIPARTITE MATCHING dana jest formuła składająca się z <math>m</math> klauzul nad <math>n</math> zmiennymi, to na wyjściu  
 
<wrongoption>zbiory <math>W, X, Y</math> mają po <math>m+n</math> elementów</wrongoption>
 
<wrongoption>zbiory <math>W, X, Y</math> mają po <math>m+n</math> elementów</wrongoption>
Linia 56: Linia 56:
  
  
<quiz>Suma podzbioru
+
<quiz>
 
W redukcji dowodzącej NP-zupełności problemu SUBSET SUM, niech zbiór wejściowy ma moc <math>3m</math>, a zbiór trójek <math>n</math>. Na wyjściu redukcji otrzymane liczby  
 
W redukcji dowodzącej NP-zupełności problemu SUBSET SUM, niech zbiór wejściowy ma moc <math>3m</math>, a zbiór trójek <math>n</math>. Na wyjściu redukcji otrzymane liczby  
 
<rightoption>reprezentują podzbiory trójelementowe</rightoption>
 
<rightoption>reprezentują podzbiory trójelementowe</rightoption>

Aktualna wersja na dzień 12:29, 25 wrz 2006

W przedstawionym dowodzie NP-zupełności problemu 3SAT

klauzula -składnikowa zastępowana jest przez klauzul

klauzula -składnikowa zastępowana jest przez 2 klauzule

wprowadzana jest kwadratowa liczba nowych zmiennych

wprowadzana jest liniowa liczba nowych zmiennych

klauzule o mniej niż 4 składnikach pozostają bez zmian


Przedstawiona redukcja dowodząca, że MAX2SAT jest problemem NP-zupełnym, jest redukcją logarytmiczną, gdyż

działa w czasie wielomianowym

rozmiar wyniku redukcji jest wielomianowy od długości formuły wejściowej

rozmiar wyniku redukcji można zapisać w pamięci

istnieje realizujący ją algorytm (maszyna Turinga) używający logarytmicznej pamięci roboczej


Na wejściu redukcji dowodzącej, że problem NODE COVER jest NP-zupełny, dana jest formuła o klauzulach nad zmiennymi. W utworzonym grafie jest

wierzchołków

krawędzi

wierzchołków

krawędzi

co najmniej krawędzi


W jaki sposób w dowodzie NP-zupełności problemu HAMILONIAN CYCLE korzysta się z tego, że gadżet można trawersować dwukrotnie, za każdym razem inną połowę gadżetu?

Konstruując pokrycie, możemy wykorzystać dwukrotne trawersowanie gadżetu

Przy konstrukcji cyklu w gadżecie, pozwala to uwzględnić sytuację, gdy oba końce krawędzi są w pokryciu

Z tego powodu zwiększa się liczbę selektorów

Z tego powodu zmniejsza się liczbę selektorów


Problem HAMILTONIAN PATH, należący do klasy NP,

jest zacieśnienieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny

jest uogólnieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny

to problem o takiej samej dziedzinie jak HAMILTONIAN CYCLE i dlatego jest NP-zupełny

to problem różny od HAMILTONIAN CYCLE, więc wymaga osobnego dowodu NP-zupełności


Jeśli na wejściu redukcji z problemu 3SAT do TRIPARTITE MATCHING dana jest formuła składająca się z klauzul nad zmiennymi, to na wyjściu

zbiory mają po elementów

zbiory mają po elementów

zbiór trójek ma elementów

zbiór trójek ma elementów

zbiór trójek ma elementów


W redukcji dowodzącej NP-zupełności problemu SUBSET SUM, niech zbiór wejściowy ma moc , a zbiór trójek . Na wyjściu redukcji otrzymane liczby

reprezentują podzbiory trójelementowe

reprezentują moce podzbiorów

są wielkości wielomianowej od i

są zapisane na bitach

są zapisane na bitach