证明了NP的完整性决定单调布尔公式的满意度

Question

我正在尝试解决这个问题，我真的很挣扎。

一个 单调布尔公式 是命题逻辑中的一个公式，所有文字都是正面的。例如，

$ 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减少到单调布尔公式。我尝试过的一件事是将虚拟变量替换为每个负面文字。例如，我尝试用$ z_1 $替换$ neg x_1 $，然后尝试强迫$ x_1 $和$ z_1 $变为不同的值。不过，我还没有能力工作。

Answer 1

您要查看的问题的“父”有时称为加权满意度（WSAT，尤其是在参数化的复杂性中）或min-on-ons（尽管这通常是一个优化版本，但足够接近）。这些问题具有“最多$ k $变量设置为True”限制作为其定义功能。

实际上，对单调公式的限制实际上很容易显示硬度，您只需要暂时出现外部可满足问题即可。我们没有尝试修改SAT实例，而是从主导集（DS）开始。

看看您是否可以从那里得到它。扰流板中有更多的东西，分解成碎片，但如果可以的话，请避免它们。我不会在NP中展示会员资格，您应该没有问题。

给定一个ds的实例$（g，k）$（即，我们想要一组最多的$ k $的主导尺寸，$ g $），我们可以构造一个$（ phi，k）$ wsat，其中公式在其中公式$ phi $是单调CNF公式：

基本结构：

对于v（g）$中的每个$ v ，我们都有一个变量$ v' in text {var}（ phi）$，对于每个$ v in v（g）$，我们都有一个条款$ c_ {v } = bigVee_ {u in n（v）} u'$。

证明的草图：

每个顶点要么必须在主体集合中，要么具有邻居，因此，如果我们可以找到形成主导集的$ k $顶点，则可以将相应的$ k $变量设置为true，以$ phi $，每个条款必须至少包含其中一个条款。同样，如果有一个重量$ k $令人满意的作业，则真实变量对应于我们在主导集中的顶点 - 每个条款$ c_ {v} $必须至少具有一个，因此每个$ v $都占主导地位（本身就是或其他）。

Answer 2

SAT有一个简单的减少。引入一个新的变量$ z_i $来表示$ neg x_i $。给定一个公式$ phi $，我们通过用$ z_i $替换$ neg x_i $的每次出现来创建一个新的公式$ phi'$，并为每个变量添加条款$ x_i vee z_i $。我们将$ k $设置为原始变量的数量。新的公式$ phi'$是单调的，并且仅当$ phi $满足时，最多可满足k变量为true。 （这是因为$ k $ discoint条款$ x_i vee z_i $会导致对$ phi'$的任何令人满意的评估，至少将$ k $变量置于true；但是最多拥有$ k $的唯一方法是完全将其中一个设置为每对{x_i，z_i}）。