中文版

所有 NP 难度证明——更一般地说，所有多项式时间约简——都遵循相同的一般大纲。为了在多项式时间内将问题 减少到问题 ，我们需要做三件事：

1. 描述一个多项式时间算法，将 的 的任意实例转换为 的特殊实例 。
2. 证明如果是的“好”实例，那么是的“好”实例。
3. 证明如果是的“好”实例，那么是的“好”实例。

让许多人感到困惑的一点是，归约算法只能“以一种方式工作”——从 到 ——但正确性证明需要“双向工作”。即正确性证明实际上并不是对称的。 “if”证明需要处理 X 的任意实例，而“only if”只需要处理约简算法产生的 Y 的特殊实例。利用这种不对称性是成功设计正确约简的关键。

我发现考虑转换证书（证明给定实例是“好”的）以及实例本身是有用的。例如，

• ** CircuitSAT ** 的证书是一组用于打开灯泡的 ** 输入 **。
• ** SAT 或 3SAT ** 的证书是 ** 令人满意的作业 **。
• ** MaxIndSet ** 的证书是一个 ** 更大的独立集 **。

要将规约到，我们实际上需要设计三种算法，即：

• 在多项式时间内将任意实例 of 转换为特殊实例 of 。
• 将 的任意证书转换为 的证书，并且
• 将 的任意证书转换为 的证书。

第二个和第三个任务是指第一个算法的输入和输出，证书变换需要是可逆的，而不是实例变换，我们永远不必变换的实例，也不需要考虑任意 的实例。只有第一个算法需要在多项式时间内运行。

例如，从 CircuitSAT 到 3SAT 的规约由三个算法组成：

• 第一个将任意 CircuitSAT 转换为 3SAT 的特殊情况。
• 第二个将 CircuitSAT 的任意令人满意的输入转换为 3SAT 的令人满意的分配。
• 第三个将 3SAT 的任意满足分配转换为 CircuitSAT 的满足输入。

规约是有效的，因为第一个算法将任何 CircuitSAT 编码为高度结构化的 SAT。SAT 的特殊结构限制了它的满足方式。3SAT 的每个令人满意的分配都必须“来自”CircuitSAT 的一些令人满意的输入。我们不必完全考虑任意 3SAT 公式。

英文版

All NP-hardness proofs-and more generally, all polynomial time reductions--follow the same general outline. To reduce problem to problem in polynomial time, we need to do three things:

1. Describe a polynomial-time algorithm to transform an arbitary instance of of into a special instance of .
2. Prove that if is a "good" instance of , then is a "good" instance of .
3. Prove that if is a "good" instance of , then is a "good" instance of .

Of course, developing a correct reduction doesn’t mean handling these three tasks one at a time. First writing down an algorithm that seems to work and then trying prove that it actually works is rarely successful, especially in time-limited settings like exams. We must develop the algorithm, the “if” proof, and the “only if” proof simultaneously.

One point that confuses many students is that the reduction algorithm only "work one way"--from to --but the correctness proof needs to "work both ways". But the correctness proofs are not actually symmetric. The “if” proof needs to handle arbitrary instances of X, but the “only if” only needs to handle the special instances of Y produced by the reduction algorithm. Exploiting this asymmetry is the key to successfully designing correct reductions.

I find it is useful to think in terms of transforming certificates--proofs that a given instance is "good"--along with the instances themselves. For example,

• A certificate for CircuitSAT is a set of inputs that turns on the light bulb.
• A certificate for SAT or 3SAT is a satisfying assignment.
• A certificate for MaxIndSet is a larger independent set.

To reduce to , we actually need to design three algorithms, that is:

• Transform an arbitrary instance of into a special instance of in polynomial time.
• Transform an arbitrary certificate for into a certificate for , and
• Transform an arbitrary certificate for into a certificate for .

The second and third tasks refer to the input and output of the first algorithm. The certificate transformation needs to be reversible, not the instance transformation. We never have to transform instance of , and we don't need to think about arbitrary instance of at all. Only the first algorithm needs to run in polynomial time.

For example, the reducetion from CircuitSAT to 3SAT consists of three algorithms:

• The first transforms an arbitrary CircuitSAT into a special case of 3SAT.
• The second transforms an arbitrary satisfying input for CircuitSAT into a satisfying assignment for 3SAT.
• The third transformms an arbitrary satisfying assignemnt for 3SAT into a satisfying input for CircuitSAT.

The reduction works because the first algorithm encodes any CircuitSAT into a highly structured SAT. The special structure of SAT restricts how it can be satisfied. Every satisfying assignment for 3SAT must "come from" some satisfying input of CircuitSAT. We don't have to think about arbitrary 3SAT formulates at all.

Reference

https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf