Ограниченное количество вхождений переменных в SAT 1-в-3

11

Есть ли известный результат по классу сложности 1-в-3-SAT с ограниченным числом вхождений переменных?

Я придумал следующее экономное сокращение с Питером Найтингейлом, но я хочу процитировать кое-что, если это известно.

Вот трюк, который мы придумали. Это показывает, что 1-в-3-SAT, ограниченный 3-мя вхождениями на переменную, является NP-завершенным и #P-завершенным (поскольку 1-в-3-SAT является) , в то время как 3-SAT, ограниченный 3-мя вхождениями, находится в P

Допустим, у нас есть более трех вхождений х. Скажем, нам нужно 6. Затем мы введем 5 новых переменных x2 - x6, эквивалентных x, и две новые переменные d1 и d2, которые гарантированно будут ложными, со следующими 6 новыми предложениями:

x  -x2 d1
x2 -x3 d1
x3 -x4 d1
x4 -x5 d2
x5 -x6 d2
x6 -x  d2

Очевидно, мы заменяем каждое вхождение x после первого на xi для некоторого i. Это дает три вхождения каждого xi и d.

Вышеприведенное устанавливает для каждого di значение false, а для всех значений xi - одно и то же значение. Чтобы увидеть это, x должен быть истинным или ложным. Если это правда, то первое предложение устанавливает x2 true и d1 false, а затем это распространяется вниз по категориям. Если x ложно, то последнее предложение устанавливает x6 ложно и d2 ложно, и оно распространяется вверх по предложениям. Это явно сильно экономно, поэтому сохраняет счет.

reference-request sat reductions Ян Гент
источник

12

Насколько мне известно, текущие "пределы" были установлены в:

Стефан Поршен, Татьяна Шмидт, Эвальд Спекенмейер, Андреас Вотцлав: XSAT и NAE-SAT линейных классов CNF. Дискретная прикладная математика 167: 1-14 (2014)

См. Также тезис Шмидта: Вычислительная сложность SAT, XSAT и NAE-SAT для линейных и смешанных формул Горна CNF.

$k$ $CNF^l_+$ $k$ $CNF^l$ $k, l \geq 3$

$3$ $CNF^3$ $l=3$

$CNF_+$

Марцио де Биаси
источник

C N F_{+}

$CNF_+$

6

(Я понимаю, что это должен быть поздний ответ; я пишу для будущих читателей)

В литературе всегда есть более сильный результат.

Кубическая планарная положительная 1-в-3 Удовлетворенность доказана NP-полной в Муре и Робсоне, Проблемы жестких и простых плиток . (Они говорят «монотонный», а не «положительный». См. Примечание добавлено в конце)

Упомянутый результат сильнее результата из тезиса Шмидта, потому что здесь график формулы ограничен, чтобы быть плоским. (На самом деле условие сильнее: они дают особый вид вложения, называемый прямолинейным врезанием)

$G_B$ $B=(X,C)$ $X\cup C$ $E:= \{ x_iC_j\ :\$ $x_i$ $C_j$ $\}$ $X$ $C$

$B=(X,C)$ $X$ $C$ $X$ $G_B$ $B$
$X$ $C$

Обратите внимание, что каждое предложение содержит ровно 3 различные переменные, а каждая переменная появляется ровно в 3 предложениях.

См. Тезис Типпенгауэра « О планарном 3-SAT и его вариантах» (2016) для вариантов «сат», которые ограничивают количество вхождений переменных.
Примечание: есть несколько вариантов, обнаруженных после публикации этого тезиса.

Добавлено примечание: результат Мура и Робсона доказал, что кубическая планарная положительная удовлетворенность 1-в-3 является NP-полной. (То есть, логическая формула не просто монотонна, она положительна (т. Е. Не содержит отрицательных литералов вообще)). К сожалению, во многих ранних работах термин «монотонный» использовался для обозначения «положительного». Сокращение Мура и Робсона не вводит отрицательные литералы. Их сокращение происходит от плоской монотонной 1-в-3-удовлетворенности в статье Лароша. Планарная 1-в-3-удовлетворенность является NP-полной . Я не мог получить эту статью, но, скорее всего, Ларош также имел в виду позитивное, говоря «монотонно». Даже если он не имел в виду это, мы можем использовать планарную позитивную удовлетворенность 1-в-3 от Мулзера и Роте. как проблема источника вместо этого.

Смотрите этот ответ на вопрос в cs.se

Кириак Антоний
источник

Ограниченное количество вхождений переменных в SAT 1-в-3

Ответы: