SAT с двумя пунктами является полиномиальным

Question

Какова сложность экземпляра SAT с k унарными предложениями и только двумя предложениями?

Я хотел бы найти статью с таким результатом... Я нашел одну статью, в которой проблема немного отличается. Все переменные появляются не более двух раз...

Answer 1

Если я правильно понимаю, это кажется линейным временем в общей длине пунктов.

Унарные предложения немедленно вызывают частичное присвоение переменной τ. Если одно из двух предложений не является выполнимым (пустым) при τ, или некоторые единичные предложения противоречат друг другу, экземпляр является неудовлетворительным. В противном случае экземпляр будет неудовлетворительным только в том случае, если два предложения единичны и дополняют τ, т. Е. X̅ и x.

Answer 2

Ваша проблема имеет complexity in O(n) где n is the total size of clauses,

У вас есть K унарных предложений, тезисы K унарных предложений можно рассматривать как поднабор переменных. Если вы не уважаете эти унарные пункты, наверняка вы не найдете решения (если оно существует).

Давайте рассмотрим пример, чтобы увидеть вашу проблему, цель состоит в том, чтобы найти значения для variables,

 variables = _ _ _ _ _ _ _ _
 problem   = 
              x1                 AND
              x4                 AND
              x7                 AND
             -x8                 AND
             -x5                 AND
              x2                 AND
              x3 OR  -x4 OR x5   AND
              x6 OR  -x1 OR x8

 with K = 5.

Потому что унарные предложения будут распространять свои значения в variablesэта проблема в основном такая же как:

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 OR  -x4 OR  x5  AND
              x6 OR  -x1 OR  x8
 with K = 0.

(Чтобы получить это, мы сделали операцию с линейным временем).

И поскольку мы уже знаем значения x4, x5, x1 и x8, эта проблема такая же, как:

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 AND
              x6
 with K = 0.

(Чтобы получить это, мы снова сделали операцию с линейным временем).

И, вызывая ту же функцию, что и в первой операции, мы получим:

 variables = x1 x2 x3 x4 -x5 x6 x7 -x8
 problem   = 
              true.
 with K = 0.

(Мы снова сделали линейную операцию по времени, чтобы получить этот вывод).

Которые дают вам окончательное решение: variables = x1 x2 x3 x4 -x5 x6 x7 -x8Как видите, найти решение можно только с помощью линейных временных операций.