complexity-theory - 将多项式决策简化为 NP 完全的示例

Question

我知道如果我将一个 NP 完全问题简化为一个未知问题P，那么我确定P本身就是 NP 完全问题。而且我知道如果我将问题P简化为 NP 完全问题，则没有结论。所以我想举一个例子来说明我们可以将一个多项式可解问题P简化为一个 NP 完全问题。

Answer 1

如果我将一个 NP 完全问题简化为一个未知问题 P，那么我确信 P 本身就是 NP 完全问题

不，这不是很好的表述。如果一个 NP 完全问题A可简化为问题P，那么我们只能说 NP 中的任何问题都可以简化为P。要说P是 NP 完全的，我们还需要知道P本身在 NP 中。

你可能想说的是

如果我将一个 NP 完全问题简化为 NP 中的某个 未知 问题P ，那么我确定P本身就是 NP 完全问题

现在到你原来的问题。

举例说明我们可以将多项式可解问题 P 简化为 NP 完全问题

考虑被称为 2-SAT 的问题：给定一个合取范式的布尔公式，使得每个析取最多包含两个变量，告诉它是否可以满足。

按照Aspvall、Plass & Tarjan (1979)的算法解决这个问题涉及构建一个隐含图并找到其所有强连通分量。该论文证明了该公式是可满足的当且仅当蕴涵图不包含包含某个变量及其否定的强连通分量。它还表明该算法在公式编码的大小上是线性的。

所以

1. 存在用于 2-SAT 的线性算法。
2. 2-SAT 可简化为称为 SAT 的无限制布尔可满足性问题。

这给出了可简化为 NP 完全问题 (SAT) 的多项式可解问题 (2-SAT) 的示例。