与10个变量满意

Question

我试图证明下一个问题是npc：

$$ a={\ langle \ phi \ rangle \ \ big |\ \ phi \ \ text {是cnf并sat。究竟在10 var是真实} \}} \} $$

我正在尝试从SAT找到多项式映射减少，但我无法找到一种方法来强迫10个变量来获得真正的分配。 我的想法是创建新的公式，10个字段，每个子句都是新的变量 $ x_i $ 与旧公式，但我看不到我的想法有用。

我会欣赏帮助。

Answer 1

您提到的问题在 $ p $ 中，所以它不是np-complete。我们知道 $ | \ phi |= n $ 因此变量的数量小于 $ n $ ，我们知道 $ a的成员$ 完全有10个真实分配。因此，通过蛮力算法检查每个可能的分配给变量。从n， $（^ {n} _ {10}）中选择10个变量，并将它们设置为 $ true $ 并将其他变量设置为 $ false $ 并检查这是一个令人满意的分配。此算法的运行时间是 $（^ {n} _ {10}）* n= o（n ^ {11}）$ 。