Условия плоскостности для SAT Planar 1-в-3

Планар 3SAT является NP-полным. Планарный экземпляр 3SAT - это экземпляр 3SAT, для которого график, построенный с использованием следующих правил, является плоским:

1. добавить вершину для каждого и ¯ х $x_i$$\bar{x_i}$
2. добавить вершину для каждого предложения $C_j$
3. добавить ребро для каждого пара$(x_i,\bar{x_i})$
4. добавить ребро из вершины (или ¯ х я ) для каждой вершины , которые представляют пункт, содержащий его$x_i$$\bar{x_i}$
5. добавить ребра между двумя последовательными переменных $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

В частности, правило 5 создает «основу», которая разделяет предложения на две отдельные области.

Планарная САТ 1-в-3 также является NP-полной.

$(x_i,x_{i+1})$

Да, ты можешь. На самом деле вы можете даже показать, что что-то сильнее, правда. Задача, известная как положительный планарный 1-в-3-SAT, является NP-полной, как показано Mulzer и Rote .

В этой версии 1-в-3-SAT для каждой входной формулы требуется, чтобы

• у вас есть три переменные в предложении, ни одна из них не отрицается
• график формулы плоский, даже если вы добавляете «основу» между переменными вершинами

Сокращение от Planar 3-SAT .