Сколько пунктов требуется для SAT, чтобы быть NP-Hard в формулах CNF?

Question

Нетрудно видеть, что SAT для формулы CNF с $ n $ Переменные и постоянное количество пунктов могут быть решены в полиноме. С другой стороны, трудно увидеть, что формула CNF с $ N $ Переменные и $ O (n) Достаточно преобразования $ достаточно для NP-твердости (рассмотрим, например, экземпляры SAT, связанные с естественной формулой для 3-окрасивости, нанесены на плоские графики).

Мы могли бы определить это формально, как $ \ text {cnfsat} -f- \ text {cnfsat} $ , семейство проблем, параметризованных функцией $ F $ , в котором экземпляры являются формулами в Cnf такими, что если у них есть $ n $ переменные, то они имеют в Большинство $ f (n) $ пункты. Исходя из этого, что я хотел бы знать, это то, что такое самая маленькая функция $ G $ такой, что мы знаем, что существует, существует $ f \ in o (g) $ такой, что $ \ text {cnfsat} -f- \ text {cnfsat} $ уже np-hard. Мы знаем, что G= 1 (постоянный # положения) не работает, а $ g= n $ (линейное количество пунктов) работает.

Как насчет $ g=log n $ ? Есть ли простые алгоритм для CNFSAT по формулам, имеющим $ O (\ lg \ lg n) $ clauses?

Answer 1

нижняя граница. для $ g \ le c \ cdot \ sqrt {\ log n} $ существует алгоритм полинома Отказ Идея заключается в следующем: если некоторые пункты имеют слишком много переменных, то следует тривиально выбрать некоторую переменную, чтобы удовлетворить этот пункт, не повреждая положения с несколькими переменными. Мы повторяем следующее:

Найти пункт с наименьшим количеством переменных. Пусть $ x_1, \ ldots, x_k $ Будьте переменными, участвующие в этом пункте.

.
• Если $ k> g $ , то вся формула удовлетворялась (мы обрабатываем предложения по одному и выберите переменную, которую мы не выбрали раньше).
• В противном случае мы удаляем предложение. Мы также удаляем $ x_1, \ ldots, x_k $ от всех других пунктов.

Теперь мы должны удовлетворить удаленные пункты. Поскольку на большинстве $ g $ пункты, и каждый из них представляет максимально $ g $ Новые переменные, Это означает, что в большинстве $ g ^ 2= c ^ 2 \ cdot \ log n $ Переменные в целом. Следовательно, есть больше всего $ n ^ {c ^ 2} $ Переменные комбинации, и мы можем просто использовать грубую силу.

<Сильная> Условная верхняя граница. Это почти плотно в следующем смысле. Предположим, что нижняя граница на сидел с $ n $ Переменные и $ \ GE C \ CDOT N $ пункты (для некоторых $ C $ , например, идущий из $ 3 $ -Coloring ) это $ \ alpha ^ n $ ( $ \ alpha \ in (1, 2] $ ). Обратите внимание, что такая же нижняя граница держит после нашей преобразования (поскольку мы можем просто применить его перед любым алгоритмом). Следовательно, если есть хотя бы $ \ log ^ {1+ \ epsilon} n $ пункты, они могут иметь $ \ FRAC {\ log ^ {1+ \ epsilon} n} c $ Переменные и нижняя оценка для работы Наша проблема

$$ \ alpha ^ {\ frac {\ log ^ {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ cdot \ log \ alpha} {c}}, $$

который является супер-полином.