Сат в P, если есть экспоненциально много предложений в количестве переменных?

Question

Я определяю длинный CNF Содержать как минимум $ 2^ frac {n} {2} $ clauses, где $ n $ - это число его переменных. Пусть $ text {long-sat} = { phi: phi $ является удовлетворительной длинной формулой CNF $ } $.

Я хотел бы знать, почему $ text {long-sat} in p $. Сначала я думал, что это $ text {npc} $, так как я могу сделать сокращение многочленного времени от $ text {sat} $ до $ text {long-sat} $, нет?

Но, может быть, я смогу уменьшить $ text {2-sat} $ до $ text {long-sat} $? Как я могу это сделать?

Answer 1

Если я что -то не упускаю, это тривиально в п Поскольку длина формулы является экспоненциальной по количеству переменных. Следовательно, все назначения истины $ 2^{n} $ могут быть сгенерированы и проверены в полиномиальное время в длине формулы.

Answer 2

В этом случае ответ тривиальный как Люк отмечает. Анкет Однако, как вы, кажется, придумали определение самостоятельно, обратите внимание на это.

Для SAT были обнаружены так называемые фазовые переходы, касающиеся соотношения счета переменных к количеству пунктов [1,2]. Если он маленький, экземпляры просты и трудны, если он большой. Похоже, что более или менее резкий переход от легкого к сложному. Это кажется активная область исследований. cstheory.se есть еще немного об этом явлении.

Итак, если вы настраиваете свое определение «долго», чтобы Полиномиальный Взорвать, вы действительно можете получить нетривиально легкий класс-то есть в P-просто потому, что у вас гораздо больше предложений, чем переменных.

---

1. Переход фазы SAT IP Gent (1994)
2. Определение вычислительной сложности из характерных «фазовых переходов» R. Monasson, R. Zecchina et al. (1999)