Докажите NP-полноту определения выполнимости монотонной булевой формулы

Я пытаюсь решить эту проблему, и я действительно борюсь.

Монотонная булева формула представляет собой формулу в логике высказываний , где все литералы являются положительными. Например,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

является монотонной булевой функцией С другой стороны, что-то вроде

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

не является монотонной булевой функцией.

Как я могу доказать NP-полноту для этой задачи:

Определите, выполнима ли монотонная булева функция, если переменных или меньше установлены в ?$k$$1$

Ясно, что все переменные можно просто установить положительными, и это тривиально, поэтому существует ограничение на положительно установленных переменных.$k$

Я пробовал сокращение от SAT до монотонной логической формулы. Одна вещь, которую я попробовал, - заменить фиктивную переменную на каждый отрицательный литерал. Например, я попытался заменить на , а затем попытался заставить и иметь разные значения. Я не совсем смог заставить это работать, хотя.$\neg x_1$$z_1$$x_1$$z_1$

«Родитель» проблемы, которую вы рассматриваете, иногда называется взвешенной удовлетворенностью (WSAT, особенно в параметризованной сложности) или минимальными (хотя обычно это версия оптимизации, но достаточно близкая). Эти проблемы имеют ограничение «не более переменных, установленное в истинное», как их определяющая особенность.$k$

Ограничение монотонных формул на самом деле удивительно легко показать, для чего нужно, просто нужно на мгновение выйти за рамки проблем с выполнимостью. Вместо того, чтобы пытаться изменить экземпляр SAT, мы вместо этого начинаем с Dominating Set (DS).

Посмотрим, сможете ли вы получить это оттуда. Больше в спойлерах, разбитых на куски, но избегайте их, если можете. Я не буду показывать членство в NP, у вас не должно быть проблем с этим.

Учитывая экземпляр DS (т.е. мы хотим, чтобы доминирующий набор размера не превышал для ), мы можем построить экземпляр WSAT, где формула является монотонной формулой CNF:$(G, k)$$k$$G$$(\phi,k)$$\phi$

Основная конструкция:

Для каждого у нас есть переменная , для каждого есть предложение .$v\in V(G)$$v' \in \text{var}(\phi)$$v \in V(G)$$c_{v} = \bigvee_{u\in N(v)} u'$

Эскиз доказательства:

Каждая вершина должна находиться в доминирующем множестве или иметь соседа, поэтому если мы можем найти вершин, которые формируют доминирующий набор, соответствующие переменные могут быть установлены в true в , и каждое предложение должно содержать в хотя бы один из них. Точно так же, если существует вес удовлетворяющий присваиванию, истинные переменные соответствуют вершинам, которые мы помещаем в доминирующий набор - каждое предложение должно иметь по крайней мере один, поэтому каждый доминирует (сам по себе или иным образом).$k$$k$$\phi$$k$$c_{v}$$v$

Существует простое сокращение с SAT. Введите новую переменную для представления . Учитывая формулу , мы создаем новую формулу , заменяя каждое вхождение на и добавляя выражение для каждой переменной. Мы устанавливаем равным количеству исходных переменных. Новая формула является монотонной и выполнимой, если не более k переменных имеет значение true, если и только если выполнимо. (Это потому, что непересекающихся предложений вызывает любое удовлетворительное назначение для ¬ х я ф ф ' ¬ х я г я х я ∨ г я к ф ' ф к х я ∨ г я ф $z_i$$\neg x_i$$\phi$$\phi'$$\neg x_i$$z_i$$x_i \vee z_i$$k$$\phi'$$\phi$$k$$x_i \vee z_i$$\phi'$иметь как минимум переменных для True; но тогда единственный способ получить максимум - это установить для каждой пары ровно один из них в значение true {x_i, z_i}.)$k$$k$