Простое сокращение от 3SAT до задачи о гамильтоновом пути

19

В книге Сипсера «Введение в теорию вычислений» на стр. 286 приведено сокращение от 3SAT до задачи о гамильтоновом пути.

Есть ли более простое сокращение?

Проще говоря, я имею в виду сокращение, которое было бы легче понять (для студентов).

Есть ли сокращение, использующее линейное число переменных?

Сокращение в Sipser использует переменные, где - количество предложений, а - количество переменных. Другими словами, сокращение может увеличить размер от до . Существует ли простое сокращение, при котором размер вывода уменьшения является линейным по размеру его ввода?k n s O ( s 2 )O(kn)knsO(s2)

Если это невозможно, есть ли причина? Это подразумевало бы неизвестный результат в сложности / алгоритмах?

complexity-theory np-hard Кава
источник
Просто чтобы прояснить: вы хотите использовать функцию сокращения, которая отображает экземпляры 3SAT на экземпляры HP, или вы хотите получить доказательство, которое сокращает "3SAT в NPC?" на "HP в NPC?" (Наверное, первое) Не могли бы вы изложить доказательства, на которые вы ссылаетесь? Некоторые из нас могут не иметь книгу под рукой.
Рафаэль
@ Рафаэль, я хочу получить сокращение от 3SAT до HamPath.
Каве
Сокращение в Sipser - долгое использование гаджетов, я предпочитаю не повторять здесь сокращение. Вы можете интерпретировать первый вопрос как: есть ли простое сокращение?
Каве
2
@Kaveh Я считаю, что слайды лекций здесь довольно просты: cbcb.umd.edu/~carlk/bioinfo-lectures/sat.pdf Они уменьшают 3sat до Ham. Цикл и Хэм. Цикл до Хэма. Путь. Они были первым хитом «сокращения с 3sat до гамильтонова пути», но, вероятно, не ответили на ваш второй вопрос.
Джо
1
@Kaveh: хороший вопрос, особенно "Это будет означать неизвестный результат в сложности / алгоритмах?" часть :-). Я не эксперт, но мне бы хотелось, чтобы его спросили о теории.
Vor

Ответы:

7

Число вершин в известном сокращении с 3SAT на направленный гамильтонов путь (dHAMPATH) может быть легко уменьшено до , где n - количество переменных, а k - количество предложений, поэтому размер Экземпляр построенного графа является линейным по отношению к размеру исходного экземпляра 3SAT.O(n+k)nk

В исходном сокращении у нас есть начальная и конечная вершины, вершин для предложений, n списков длиной 4 k для переменных. Идея состоит в том, что нам не нужно составлять список длиной 4 k для каждой переменной, мы можем построить список в соответствии с номером, который переменная появляется во всех пунктах. Поскольку общее количество появлений переменных в предложениях равно 3 k , оно равно O ( n + k ) .kn4k4k3kO(n+k)

куб.см
источник