Złożoność obliczeniowa/Test 5: Problemy NP-zupełne

Z Studia Informatyczne
< Złożoność obliczeniowa
Wersja z dnia 12:29, 25 wrz 2006 autorstwa Rogoda (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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