Łatwa redukcja z 3SAT do problemu ścieżki Hamiltonian

19

W książce Sipsera „Wprowadzenie do teorii obliczeń” na stronie 286 zmniejszono z 3SAT do problemu ścieżki Hamiltona.

Czy istnieje prostsza redukcja?

Mówiąc prościej, mam na myśli redukcję, która byłaby łatwiejsza do zrozumienia (dla studentów).

Czy istnieje redukcja wykorzystująca liniową liczbę zmiennych?

Redukcja w Sipserze wykorzystuje zmienne , gdzie jest liczbą klauzul, a jest liczbą zmiennych. Innymi słowy, możliwe jest, aby redukcja wydmuchała rozmiar od do . Czy istnieje prosta redukcja, w której wielkość wyniku redukcji jest liniowa względem wielkości jej wejścia?k n s O ( s 2 )O(kn)knsO(s2)

Jeśli nie jest to możliwe, czy istnieje powód? Czy oznaczałoby to nieznany wynik w złożoności / algorytmach?

complexity-theory np-hard Kaveh
źródło
Żeby było jasne: czy chcesz funkcję redukcji, która mapuje instancje 3SAT na instancje HP, czy też potrzebujesz dowodu, który redukuje „3SAT w NPC?” na „HP w NPC?”? (Chyba pierwszy). Czy możesz przedstawić dowód, do którego się odwołujesz? Niektórzy z nas mogą nie mieć książki pod ręką.
Raphael
@ Rafael, chcę redukcję z 3SAT do HamPath.
Kaveh
Redukcja w Sipserze to gadżety długotrwałego użytku, wolę nie powtarzać tutaj redukcji. Pierwsze pytanie można zinterpretować jako: czy istnieje prosta redukcja?
Kaveh
2
@Kaveh Uważam, że slajdy z wykładami są dość łatwe do naśladowania: cbcb.umd.edu/~carlk/bioinfo-lectures/sat.pdf Zmniejszają 3sat do Ham. Cykl i szynka. Jedź do szynki. Ścieżka. Były dogodnie pierwszym hitem dla „redukcji z 3sat na ścieżkę hamiltonowską”, ale prawdopodobnie nie odpowiadają na drugie pytanie.
Joe
1
@Kaveh: fajne pytanie, zwłaszcza „Czy oznaczałoby to nieznany wynik w złożoności / algorytmach?” część :-). Nie jestem ekspertem, ale chciałbym, aby zapytano go o cstheory.
Vor

Odpowiedzi:

7

Liczbę wierzchołków w znanej redukcji z 3SAT do ukierunkowanej ścieżki hamiltonowskiej (dHAMPATH) można łatwo zmniejszyć do , gdzie jest liczbą zmiennych, a jest liczbą klauzul, a zatem wielkości skonstruowana instancja graficzna jest liniowa do rozmiaru oryginalnej instancji 3SAT.n kO(n+k)nk

W pierwotnej redukcji mamy wierzchołek początkowy i końcowy, wierzchołków dla klauzul, list długości dla zmiennych. Chodzi o to, że nie musimy konstruować listy o długości dla każdej zmiennej, możemy konstruować listę zgodnie z liczbą, która pojawia się we wszystkich klauzulach. Ponieważ łączna liczba wystąpień zmiennych w klauzulach wynosi , jest to .n 4 k 4 k 3 k O ( n + k )kn4k4k3kO(n+k)

cc
źródło