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

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? $O(kn)$ $k$ $n$ $s$ $O(s^2)$

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

@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

@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

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. $O(n+k)$ $n$ $k$

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 . $k$ $n$ $4k$ $4k$ $3k$ $O(n+k)$

— cc
źródło