Вариант Критического САТ в ДП

Язык входит в класс если есть два языка и такие чтоD P L 1 ∈ N P L 2 ∈ c o N P L = L 1 ∩ L $L$$DP$$L1 \in NP$$L2 \in coNP$$L = L1 \cap L2$

Канонической -полной проблемой является SAT-UNSAT: учитывая два выражения 3-CNF, и , верно ли, что выполнимо, а нет?F G F $DP$$F$$G$$F$$G$

Известно также, что критическая проблема SAT является полной: если задано 3-CNF-выражение , верно ли, что неудовлетворительно, но удаление любого предложения делает его удовлетворительным?F $DP$$F$$F$

Я рассматриваю следующий вариант проблемы Critical SAT: учитывая выражение из 3-CNF , верно ли, что выполнимо, но добавление любого 3-предложения (из но с использованием тех же переменных, что и ) делает его неудовлетворительным? Но мне не удается найти сокращение от SAT-UNSAT или даже доказать, что это или трудно.F F F N P c o N $F$$F$$F$$F$$NP$$coNP$

Мой вопрос: является ли этот вариант DP-полным?

Спасибо за ответ.

[Я сделал это в правильный ответ, потому что кто-то дал это -1]

Если какое-либо предложение разрешено добавлять, то язык будет пустым - очевидно, что к любой выполнимой формуле можно добавить 3-предложение c, составленное из переменных, которые не появляются в F : F ∪ { c } будет выполнимым.$F$$c$$F$$F \cup \{ c \}$

Если добавленные предложения должны использовать переменные , то язык находится в P.$F$

Обоснование заключается в следующем:

Возьмем любой , то есть F ∈ S A T и для любого 3-п с о переменных F , F ∪ { C } ∈ U N S T . Скажите c = l 1 ∨ l 2 ∨ l 3 ∉ F , где l i - литерал. Поскольку F ∪ { c } является UNSAT, все модели F должны иметь l $F \in L$$F \in SAT$$c$$F$$F \cup \{c\} \in UNSAT$$c = l_1 \lor l_2 \lor l_3 \notin F$$l_i$$F \cup \{ c \}$$F$ (для i = 1 , 2 , 3 ) - потому что если в некоторой модели, например, l 1 = 1 , то она будет удовлетворять c, и поэтому F ∪ { c } . Теперь предположимчто существует другое условие C ' , которое так жекак с , но с одним или более буквальным переворачивается такимчто с ' ∉ F , скажем , гр ' = ¬ л 1 ∨ л 2 ∨ л $l_i=0$$i=1,2,3$$l_1=1$$c$$F \cup \{c\}$$c'$$c$$c' \notin F$$c' = \neg l_1 \lor l_2 \lor l_3$, Тогда по тому же аргументу все модели должны иметь l 1 = 1 . Таким образом, необходимым условием для F ∈ L является то, что для каждого предложения c ∈ F есть ровно 6 других предложений в F, которые используют три переменные c - давайте назовем эти подмножества из 7 предложений F- блоков . Обратите внимание, что каждый блок подразумевает уникальное удовлетворяющее присваивание его переменным. Когда это необходимое условие выполнено, F либо однозначно выполнимо, либо неудовлетворительно. Два случая можно различить, проверяя, являются ли назначения, подразумеваемые блоками $F$$l_1 = 1$$F \in L$$c \in F$$F$$c$$F$ $F$$F$ Столкновение, которое можно четко сделать в линейном времени.

Могу ли я предложить ответ на свой вопрос благодаря вашим комментариям: вариант Critical SAT находится в P.

Давайте назовем «Задача 1» вариантом критического SAT: учитывая 3-CNF выражение , верно ли, что F выполнимо, но добавление любого предложения из F делает его неудовлетворительным?$F$$F$$F$

И "Проблема 2": учитывая выражение из 3-CNF , верно ли, что F содержит все предложения, которые оно подразумевает, и имеет уникальную модель?$F$$F$

Учитывая формулу 3-CNF, .$F$

Если является да экземпляром задачи 2, то любой пункт из F не вытекают F , а затем покрывает только один возможное удовлетворяющее назначение для F . Добавление такого условия в F делает его неустранимым. Следовательно, F является положительным примером проблемы 1.$F$$F$$F$$F$$F$$F$

Если является не экземпляром задачи 2, то: Случай 1: она существует пункт из F , которая вытекающая F . Тогда добавление этого предложения к F не изменит его выполнимости. Следовательно, F не является проблемой 1. Случай 2: F содержит все предложения, которые он подразумевает, но не удовлетворяет требованиям. Следовательно, F не является проблемой 1. Случай 3: F содержит все предложения, которые он подразумевает, но имеет как минимум 2 разные модели. Как подчеркивает комментарий Каве, «предположим, что модели различаются по переменной p, то добавление предложения, содержащего его, не изменит выполнимости. » F , следовательно, не является проблемой 1.$F$$F$$F$$F$$F$$F$$F$$F$$F$

$F$$F$

$F$ n(n-1)(n-2$\binom{n}{3}$$\frac{n(n-1)(n-2)}{3}$$n$