SAT 1-в-3 остается NP-жестким, даже если каждая переменная встречается как положительно, так и отрицательно?

Стандартная проблема 1-в-3 SAT (или XSAT или X3SAT):
Экземпляр : формула CNF с каждым предложением, содержащим ровно 3 литерала.
Вопрос : есть ли удовлетворительная установка присваивания, точно равная 1 литералу на предложение, верно?

Проблема является NP-полной и остается сложной, даже если никакая переменная не встречается отрицательной. Интересно, становится ли эта проблема легкой или остается сложной, если требуется, чтобы каждая переменная возникала хотя бы один раз положительно и хотя бы раз отрицательно ?

Обычное сокращение от 3SAT, показывающее, что 1-в-3 SAT трудно заменить пункт $(x\lor y \lor z)$ по пунктам $(\lnot x \lor a \lor b)$, $(y\lor b\lor c)$, $(\lnot z \lor c \lor d)$ где $a,b,c,d$свежи для каждого пункта. Таким образом, это сокращение не помогает в ответе на мой вопрос. У меня были проблемы с созданием гаджета, показывающего сложность этого варианта, поскольку, если ровно 1 литерал в предложении истинен, то несимметрично 2 литерала ложны. Если это окажется легким, то можно подумать о терминах набора предложений, но я не понимаю, как это сделать.

В комментарии OP выразил заинтересованность в сокращении, которое породило экземпляры с 3 различными переменными в предложении. Вот простой подход:

Сокращение от SAT 1-в-3 с 3 различными переменными в предложении:

• Прежде всего, включите все предложения в формулу ввода как предложения в формулу вывода.
• Во-вторых, введите три новые переменные $F_1$, $F_2$, а также $F_3$ и добавьте следующие три предложения в формулу вывода: $(\neg F_1, F_2, F_3)$, $(F_1, \neg F_2, F_3)$, а также $(F_1, F_2, \neg F_3)$,
• Наконец, для каждой переменной $x$ в исходной формуле введите новую переменную $x'$и добавьте следующие два предложения в формулу вывода: $(x, x', F_1)$ а также $(\neg x, \neg x', F_1)$,

Давайте проверим, что это сокращение делает то, что мы хотим. Следующие свойства - это то, что мы хотим:

1. Каждое предложение всегда имеет три различных переменных.
2. Каждая переменная встречается в некотором предложении положительно, а в другом - отрицательно.
3. Формула ввода эквивалентна формуле вывода.

Свойство 1 тривиально проверить. Свойство 2 также легко проверить: переменные$F_1$, $F_2$, а также $F_3$ каждая из них встречается как положительно, так и отрицательно в предложениях, добавленных во втором пункте маркированного списка, в то время как каждая другая переменная в формуле встречается как положительно, так и отрицательно в предложениях, добавленных в третьем пункте маркированного списка.

Что касается свойства 3, это менее тривиально, но все же легко. Вы можете легко утверждать, что единственное назначение для переменных$F_1$, $F_2$, а также $F_3$ что удовлетворяет каждому пункту из второго пункта пули, состоит в том, чтобы сделать все три $F_i$s false. But then assuming a value of false for $F_1$, пункты $(x, x', F_1)$ а также $(\neg x, \neg x', F_1)$ добавленные в третьем пункте пули выполняются тогда и только тогда, когда $x' = \neg x$, Поскольку нет никаких других ограничений на$x'$, это означает, что всегда можно расширить удовлетворяющее назначение для входной формулы в удовлетворяющее назначение для выходной формулы: просто установите каждый $x'$ быть отрицанием соответствующего $x$ и установить каждый $F_i$ ложно.