Уникальный 3SAT для уникального 1-в-3Сат

Question

Предположим, у меня есть формула CNF с пунктами размера 2 и 3. Он имеет уникальное удовлетворение.

Это было сделано из бинарной схемы умножения, где я умножую два числа простых чисел A и B таким, что A * B= S где S - полупроизводительный номер. Я добавил условия, которые a!= 1, b!= 1 и a <= b, затем добавляли значение s к формуле Убедитесь, что назначение уникально. Единственный способ удовлетворить формулу состоит в том, чтобы поставить значения простых простых преданков A и B в правильном порядке на входных битах.

в 1-in-3SAT, мы заставляем то, что ровно 1 литерал должен быть правдой в каждом триплетном и двух других ложном. Если ровно 2 литерала верны, мы можем перевернуть все итералы в пункте, чтобы получить эквивалентный 1-в-3SAT пункт (другими словами 2-в-3SAT - это та же проблема).

Базовое наблюдение: в то время как регулярное или пункт исключает 1 возможность из 8, предложение 1-in-3 устраняет 5 возможностей из 8.

3SAT может быть уменьшен до 1-в-3 SAT, так что, если формула 3SAT выполнена, то, как и уменьшенная формула.

Тем не менее, сокращения, похоже, не сохраняют количество заданий, введя новые переменные, не заставляя их значение.

Может уникальный 3SAT будет уменьшен до уникального 1-в-3SAT ...

1. , не зная правильного назначения?
2. Если нет, зная правильное задание?

Answer 1

Да, 3-SAT Formula $ \ phi $ может быть преобразован в формулу SAT 1-in-3 $ \ phi '$ При сохранении количества удовлетворяющих заданий. Чтобы избежать неоднозначности, я буду использовать « $ \ vee $ " между литералами 3-SAT оговорка и запятыми между литералами 1-в-3 пункта SAT. < / P >.

---

Позвольте мне предварительно показать это, учитывая два литерала $ a $ и $ B $ , мы можем Имитация нового типа предложения $ (x= a \ quild b) $ , который заставляет значение новой переменной $ x $ Быть $ a \ quctge b $ Используя только 1-в-3 SAT ограничения, не вводя какое-либо новое решение.

Рассмотрим клавиши: $$ (\ rovline {b}, c, x) \ клин (A, C, D) \ клин (\ rovline {a}, e, x) \ клин (б, е, е) $$

Если $ a=top $ и $ b=top $ , то 2-й и 4-е положения гарантируют, что $ C= D= E= f=bot $ . Затем 1-й и 3-я положения гарантируют, что $ x=top $ .

Если $ a=top $ и $ b=bot $ , затем 2-й Предложение гарантирует, что $ C= D=Bot $ . Затем 1-й момент гарантирует, что $ x=bot $ . 3-й пункт гарантирует, что $ e=top $ , а 4-е главное означает $ f=bot $ .

Дело $ a=bot $ и $ b=top $ симметричен.

Если $ a=bot $ и $ b=bot $ , затем 1-й и 3-е положения подразумевают $ c= e= x=bot $ . 2-й и 4-й положения обеспечивают $ d= f=top $ .

---

Теперь я готов трансформировать формулу $ \ phi $ 3sat к формуле $ \ phi '$ < / SPAN> от 1-в-3 SAT. Рассмотрим теперь предложение $ (A \ vee b \ vee c) $ $ \ phi $ . Это может быть преобразовано в следующие эквивалентные 1-in-3 SAT CLASES:

.

• Добавить новую переменную $ x $ , это true iff $ a $ неверно и $ b $ true. Это кодируется предложением $ (x=unverline {a} \ enge b) $ .

• Добавить новую переменную $ y $ Это true iff $ a $ false , $ b $ неверно, а $ C $ true. Нам понадобится дополнительная переменная $ Z $ . Пункт $ (z=averline {a} \ q=averline {b}) $ гарантирует, что $ z $ < / span> true, если и только если $ a $ неверно и $ b $ неверно. Затем значение $ y $ может быть применена в соответствии с пунктом $ (y= z \ q ve recge c) $ .

• Если $ (a \ vee b \ vee c) $ верно, по меньшей мере, один из $ a $ , $ b $ или $ c $ true. Это означает, что именно один из $ a $ , $ x $ и $ y $ верно. На общение, если $ (a \ vee b \ vee c) $ неверно, то вообще $ A $ , $ x $ и $ y $ неверно. Это показывает, что $ (a \ vee b \ vee c) $ удовлетворяет, если и только если $ (A, X, y $ ) удовлетворяется.

Затем мы построили эквивалентную формулу SAT 1-in-3 $ \ phi '$ , который использует суперсент переменных оригинальной формулы 3 SAT $ \ phi $ . Назначение истины для переменных $ \ phi '$ удовлетворяет $ \ phi' $ если и только если Назначение ограничено переменными $ \ phi $ удовлетворяет возможности $ \ phi $ . Следовательно, если введен какое-либо новое решение для $ \ phi '$ , он должен быть из-за вновь добавленных переменных $ x $

n>, $ y $ и $ Z $ (один набор для каждого пункта).Однако значения этих переменных полностью определяются значениями переменных $ \ phi $ .

Answer 2

Такое уменьшение описано в Приложении B Régis Barbanchon, На уникальном графике 3-Окрашимость и сосредоточенные сокращения в плоскости .Барбанчон приписывает его до предыдущей работы ([9] в библиографии).В другом месте я видел атрибуцию отмеченной бумаги Шефера, в которой он доказывает свою знаменитую теорему дихотомии, среди остальных, которые дают сокращение от 3SAT до 1-в-3Сат, что предположительно сорвано (я не проверил).