Улучшение общего сокращения Кука для Clique to SAT?

10

Я заинтересован в уменьшении клика до SAT, не делая экземпляр намного больше.k

Клика находится в NP, поэтому ее можно уменьшить до SAT, используя логарифмическое пространство. Простое сокращение учебника Garey / Johnson увеличивает размер экземпляра до кубического размера. Тем не менее, Клик находится в P для каждого фиксированного k, так что «должно быть» эффективное снижение, по крайней мере, для фиксированного k .kkk

Одним из способов создания сокращения является использование переменных SAT в качестве характеристического вектора , для переменной которого установлено значение true, указывающее, что связанная вершина находится в клике. Это уменьшение является естественным, но создает экземпляр SAT квадратичного размера, если график разрежен. Для разреженного графа требуется квадратично много предложений для обеспечения того, чтобы в каждой паре несмежных вершин в клике могла находиться не более одной вершины.

Давайте попробуем сделать лучше, чем .O(n2)

Общее сокращение Cook / Schnorr / Pippenger / Fischer работает, сначала принимая ограниченный по времени NDTM, который определяет язык, моделируя NDTM с помощью забывающего DTM, моделируя забывающий DTM с помощью схемы, а затем моделируя схему с помощью 3 -SAT экземпляр. Это создает экземпляр 3-SAT размером если временная граница NDTM равна t ( n ) . Коэффициент логарифма кажется неизбежным из-за накладных расходов при моделировании забытой машиной. Для k- клика, кажется, есть t (О(T(N)журналT(N))T(N)К , что дает экземпляр 3-SAT размером O ( n k ( log n + log k ) ) , который являетсяквазилинейнымдля фиксированного k . В своей статье 1988 года Кук спросил, существует ли лучшее общее сокращение для языков в NP, и, насколько я знаю, это все еще открыто. Тем не менее, Clique имеет много структуры, поэтому, возможно, в этом случае можно добиться большего.T(N)знак равноО(NК)О(NК(журналN+журналК))К

Известно ли лучшее сокращение от Clique до SAT?

В частности, возможно ли для фиксированного уменьшить k -Clique до SAT, сохраняя при этом увеличение размера экземпляра линейным? Или можно использовать существующий результат, чтобы доказать, что это вряд ли возможно? Я пытался использовать Fortnow / Santhanam и Dell / van Melkebeek, но накладные расходы кажутся слишком большими для этих результатов, чтобы подразумевать что-то конкретное.КК

(Я работал с сокращением, которое, по-видимому, избегает логарифмического фактора, но прежде чем тратить больше времени на кровавые подробности, чтобы проверить его правильность, я хотел бы знать, известно ли уже такое сокращение или маловероятно, что существовать.)

Андраш Саламон
источник
См. Несколько связанный вопрос mathoverflow.net/q/224898/440 о MathOverflow, в котором небольшой размер количественной булевой формулы для клика напрямую переводит в медленную скорость сходимости закона 0-1 для случайных графов. Вопрос уже содержит формулу квадратичного размера; Принятый ответ дает формулу линейного размера, которая подразумевает существование k- клика, но это может быть ложным, даже если существует клика. КК
Дэвид Эппштейн
Вы хотите сокращение, которое также выполняется в пространстве журнала? Поскольку, как вы указали , -clique может быть решена за полиномиальное время для константы k , поэтому сокращение за полиномиальное время может фактически проверить k -clique и затем вывести экземпляр SAT постоянного размера. ККК
Джо Бебель
@JoeBebel: с помощью space можно даже вывести экземпляр SAT с k log n переменными, решениями которого являются все положения k -кликов на графике. Для каждой потенциальной клики выдается предложение, запрещающее этот k -clique, если его нет. Это точно отражает решения, сокращение один к одному, поэтому отвечает на вопрос Каве, но, как и в случае с вашим предложением, решение вопроса до принятия решения о том, как уменьшить его, кажется слишком большим обманом. КжурналNКжурналNКК
Андраш Саламон

Ответы:

8

Вы можете выразить -clique как экземпляр SAT с O ( n k ) переменными и O ( n k 2 ) предложениями. Для фиксированного k это линейно по n .КО(NК)О(NК2)КN

Пусть если v - это i- я вершина в клике (по лексикографически отсортированному порядку). Другими словами, x i - это «горячая» кодировка i- й вершины в клике (это характеристический вектор для множества с одним элементом). Это вводит n k переменных.Иксяvзнак равно1vяИксяяNК

Теперь для каждого вы можете убедиться, что соответствующие две вершины соединены ребром, используя n предложений. например, одно предложение ( ¬ x i ux j v 1x j v m ), где v 1 , , v m - вершины, смежные с вершиной u . Вы получаете одно предложение на вершину u . Это вводит в общей сложности O ( n k(я,J)N(¬ИксяUИксJv1ИксJvм)v1,...,vмUU пункты.О(NК2)

Для каждого вы можете принудительно установить, что x i является вектором веса Хэмминга 1 и что x i < x i + 1 , используя предложения O ( n ) . Это добавляет в общей сложности O ( n k ) больше предложений.яИксяИкся<Икся+1О(N)О(NК)


Можно было бы сделать лучше, используя переменных для представления вершин в клике ( lg n битов достаточно для представления i- й вершины в клике), а затем построив схему, чтобы проверить, соответствует ли набор из k вершин клика Один из подходов к построению такой схемы может состоять в том, чтобы построить список всех k ( k - 1 ) / 2 пар этих вершин в отсортированном порядке, а затем сравнить его со списком ребер, используя процедуру Merge из Mergesort или что-то вроде который. Может быть возможно получить что-то вроде O ( ( nКЛ.Г.NЛ.Г.NяКК(К-1)/2 схема poly ( lg n ) ) , которая затем преобразуется в экземпляр SAT того же размера (где m = количество ребер в графе). Я не пытался проработать детали, чтобы понять, возможно ли это на самом деле.О((N+м+К2)поли(Л.Г.N))мзнак равно

DW
источник