Нахождение решения системы уравнений 2SAT отделена или (форма DNF) в NP

Question

Я хочу знать, если нахождение решения конкретного количества уравнений 2SAT Sepearded или Gate (форма DNF, как показано ниже), находится в P или NP.

Уравнение имеет общие N переменные и каждую статью - это уравнение 2SAT в подмножестве переменных от 1 до n. Пример:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

Уравнение f - это DNF уравнений 2SAT, что говорит МЛ.Находит решение для этого в NP?Если да, как?

Также, в частности, я также хочу знать, если нахождение ложных экземпляров уравнения f также в P или NP.

Answer 1

.
• сначала позвольте мне отметить, что заголовок вопроса немного вводит в заблуждение, потому что $ p $ - это подмножество $ Np $ . Смотрите также комментарий Ювальского фильма. Я предполагаю, что вы предназначали , чтобы спросить, - это ли это в $ p $ или в $ np \ setminus p $ .
• также имя "dnf" конкретно относится к дизъюнкции <сильных> элементарных союзников, а не дизъюнкция произвольных функций. То, что вы описываете, не является DNF, а дизъюнкция CNFS.

с этим, вот мой ответ.

---

1. Чтобы удовлетворить дизъюнкцию 2-CNFS, все, что вам нужно, это удовлетворить One из них. Итак, если вы примените алгоритм 2-SAT до первого из CNFS и получите «Да», то ответ на всю проблему является «да». В противном случае вы просто переходите ко второму, и так далее. Не должен занимать много времени, так как у вас только m из них. Если ни один из них не может быть удовлетворен индивидуально, то есть они все постоянные нули, то, очевидно, вся вещь - постоянная ноль.

   Так что ответ на первую часть: проблема в P, со следующим алгоритмом решений:

   Для каждого 2-CNF примените «нормальный» алгоритм 2-SAT (правило разрешения), чтобы определить, является ли он удовлетворен или нет. Если «Да», просто верните «Да». Если вы проходили все из них, не найдя «да», то верните «нет».

---

2. Теперь, найдя «ложные» случаи этой формулы (также известной как проблема тавтологии), является еще одним вопросом целиком. Для одной, тавтологии для или Инд И ОРС эквивалентны удовлетворенности для удовлетворения Анд И ОРС И Моргана. Но это просто более общий случай уже общей проблемы, не так ли?

   Рассмотрим, что произойдет, когда вы ограничите множество возможных формул для тех, в которых каждое двухэлементное дизъюнкция действительно просто один элемент, повторяется. Так что это формула, как $$ F= [(x_1 \ vee x_1) \ & (\ neg x_2 \ vee \ neg x_2) \ & (x_3 \ vee x_3)] \ vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)] \ vee ... $$ что эквивалентно $$ F= [x_1 \ & \ neg x_2 \ & x_3] \ vee [x_2 \ & x_4 \ & x_5] \ vee ... $$ который просто нормальный DNF. После преобразования De Morgan вы получаете нормальный CNF, чья удовлетворяемая удовлетворение является NP-трудным. Следовательно, любая проблема, которая включает в себя эту точку в качестве подмножества , также будет как минимум NP-Hard.

   Очевидно, проблема рассматриваемой проблемы не будет снаружи np, потому что она все еще постоянно проверяется. Таким образом, ответ на ваш второй вопрос «в NP, но не в P».