Я заинтересован в уменьшении клика до SAT, не делая экземпляр намного больше.
Клика находится в NP, поэтому ее можно уменьшить до SAT, используя логарифмическое пространство. Простое сокращение учебника Garey / Johnson увеличивает размер экземпляра до кубического размера. Тем не менее, Клик находится в P для каждого фиксированного k, так что «должно быть» эффективное снижение, по крайней мере, для фиксированного k .
Одним из способов создания сокращения является использование переменных SAT в качестве характеристического вектора , для переменной которого установлено значение true, указывающее, что связанная вершина находится в клике. Это уменьшение является естественным, но создает экземпляр SAT квадратичного размера, если график разрежен. Для разреженного графа требуется квадратично много предложений для обеспечения того, чтобы в каждой паре несмежных вершин в клике могла находиться не более одной вершины.
Давайте попробуем сделать лучше, чем .
Общее сокращение Cook / Schnorr / Pippenger / Fischer работает, сначала принимая ограниченный по времени NDTM, который определяет язык, моделируя NDTM с помощью забывающего DTM, моделируя забывающий DTM с помощью схемы, а затем моделируя схему с помощью 3 -SAT экземпляр. Это создает экземпляр 3-SAT размером если временная граница NDTM равна t ( n ) . Коэффициент логарифма кажется неизбежным из-за накладных расходов при моделировании забытой машиной. Для k- клика, кажется, есть t ( , что дает экземпляр 3-SAT размером O ( n k ( log n + log k ) ) , который являетсяквазилинейнымдля фиксированного k . В своей статье 1988 года Кук спросил, существует ли лучшее общее сокращение для языков в NP, и, насколько я знаю, это все еще открыто. Тем не менее, Clique имеет много структуры, поэтому, возможно, в этом случае можно добиться большего.
Известно ли лучшее сокращение от Clique до SAT?
В частности, возможно ли для фиксированного уменьшить k -Clique до SAT, сохраняя при этом увеличение размера экземпляра линейным? Или можно использовать существующий результат, чтобы доказать, что это вряд ли возможно? Я пытался использовать Fortnow / Santhanam и Dell / van Melkebeek, но накладные расходы кажутся слишком большими для этих результатов, чтобы подразумевать что-то конкретное.
(Я работал с сокращением, которое, по-видимому, избегает логарифмического фактора, но прежде чем тратить больше времени на кровавые подробности, чтобы проверить его правильность, я хотел бы знать, известно ли уже такое сокращение или маловероятно, что существовать.)
источник
Ответы:
Вы можете выразить -clique как экземпляр SAT с O ( n k ) переменными и O ( n k 2 ) предложениями. Для фиксированного k это линейно по n .К O ( n k ) O ( n k2) К N
Пусть если v - это i- я вершина в клике (по лексикографически отсортированному порядку). Другими словами, x i - это «горячая» кодировка i- й вершины в клике (это характеристический вектор для множества с одним элементом). Это вводит n k переменных.Икся в= 1 v я Икся я н к
Теперь для каждого вы можете убедиться, что соответствующие две вершины соединены ребром, используя n предложений. например, одно предложение ( ¬ x i u ∨ x j v 1 ∨ ⋯ ∨ x j v m ), где v 1 , … , v m - вершины, смежные с вершиной u . Вы получаете одно предложение на вершину u . Это вводит в общей сложности O ( n k( я , j ) N ( ¬ xя тебя∨ хJ V1∨ ⋯ ∨ xJ Vм) v1, … , Vм U U пункты.O ( n k2)
Для каждого вы можете принудительно установить, что x i является вектором веса Хэмминга 1 и что x i < x i + 1 , используя предложения O ( n ) . Это добавляет в общей сложности O ( n k ) больше предложений.я Икся Икся< хя + 1 O ( n ) O ( n k )
Можно было бы сделать лучше, используя переменных для представления вершин в клике ( lg n битов достаточно для представления i- й вершины в клике), а затем построив схему, чтобы проверить, соответствует ли набор из k вершин клика Один из подходов к построению такой схемы может состоять в том, чтобы построить список всех k ( k - 1 ) / 2 пар этих вершин в отсортированном порядке, а затем сравнить его со списком ребер, используя процедуру Merge из Mergesort или что-то вроде который. Может быть возможно получить что-то вроде O ( ( nк лгN Л.Г.N я К k ( k - 1 ) / 2 схема poly ( lg n ) ) , которая затем преобразуется в экземпляр SAT того же размера (где m = количество ребер в графе). Я не пытался проработать детали, чтобы понять, возможно ли это на самом деле.O ( ( n + m + k2) поли ( LGн ) ) м =
источник