为什么我们要在 NP-completeness reduction 中选择来源？
Why do we get to pick the source in an NP-completeness reduction?
我们知道要证明问题A是NP完全的，我们必须
找到从 NP 完全问题 B 到这个问题 A 的多项式时间减少。
例如，我们可以做这些减少：
SAT ---> clique
SAT ---> independent set
Independent set ---> Vertex Cover
为什么我们要选择使用哪个 NP 完全问题作为归约的来源？是不是所有NP完全问题都可以相互归约，我们只需要选择一个更容易证明归约的问题？
我的意思是很容易显示从 SAT 到 clique 的减少。但是，我不知道如何显示从 SAT 到 Vertex Cover 的减少，但我知道如何从 Independent Set 减少到 Vertex Cover。原则上是否可以将每个 NP-Complete 减少为每个其他 NP-Complete，但我们只使用最简单的一个？
一个问题是 NP-complete if
- 它在 NP 中，并且
- NP 中的每个问题都可以多项式时间归约到它。
这意味着如果你处理任何两个 NP 完全问题，你就可以保证它们在多项式时间内可以相互归约，即使你并不确切知道这种归约会是什么样子.
您问为什么在证明 NP 完全性时要选择哪个 NP 完全问题作为归约源。原因是一旦你证明了一些 NP 完全问题 A 减少到 NP 问题 B，你可以得出结论 every NP-complete problem C 减少到 B，因为 C 减少到 A 和 A 减少到 B。换句话说，如果您通过将任何已知的 NP 完全问题减少到它来证明问题是 NP 完全的，那么原则上您可以减少 every NP完全问题吧。您只是通过减少使减少最容易做到的问题来使事情变得简单。
如果您选择了错误的 NP 完全语言作为源，那么在实践中进行归约可能会非常困难。要了解这是为什么，请考虑 Cook-Levin 定理（SAT 是 NP 完全）的证明是如何工作的。为了表明您可以将任何 NP 问题简化为 SAT，您从针对该问题的多项式时间非确定性图灵机开始，然后使用它来构建一个大量的命题公式，基本上说 "there is some computation of this TM that accepts its input string." 这在理论上很棒，但在实践中，这是一个可怕的减少，对于任何看过它的人来说几乎是完全无法理解的。任何时候你通过对一个已知的 NP 完全问题进行归约来证明问题的 NP 完全性时，都可以将其视为找到一条捷径来跳过一个非常困难的证明——如果你能找到一些简单而美好的东西，你就跳过减少的庞然大物。
我们知道要证明问题A是NP完全的，我们必须 找到从 NP 完全问题 B 到这个问题 A 的多项式时间减少。
例如，我们可以做这些减少：
SAT ---> clique
SAT ---> independent set
Independent set ---> Vertex Cover
为什么我们要选择使用哪个 NP 完全问题作为归约的来源？是不是所有NP完全问题都可以相互归约，我们只需要选择一个更容易证明归约的问题？
我的意思是很容易显示从 SAT 到 clique 的减少。但是，我不知道如何显示从 SAT 到 Vertex Cover 的减少，但我知道如何从 Independent Set 减少到 Vertex Cover。原则上是否可以将每个 NP-Complete 减少为每个其他 NP-Complete，但我们只使用最简单的一个？
一个问题是 NP-complete if
- 它在 NP 中，并且
- NP 中的每个问题都可以多项式时间归约到它。
这意味着如果你处理任何两个 NP 完全问题，你就可以保证它们在多项式时间内可以相互归约，即使你并不确切知道这种归约会是什么样子.
您问为什么在证明 NP 完全性时要选择哪个 NP 完全问题作为归约源。原因是一旦你证明了一些 NP 完全问题 A 减少到 NP 问题 B，你可以得出结论 every NP-complete problem C 减少到 B，因为 C 减少到 A 和 A 减少到 B。换句话说，如果您通过将任何已知的 NP 完全问题减少到它来证明问题是 NP 完全的，那么原则上您可以减少 every NP完全问题吧。您只是通过减少使减少最容易做到的问题来使事情变得简单。
如果您选择了错误的 NP 完全语言作为源，那么在实践中进行归约可能会非常困难。要了解这是为什么，请考虑 Cook-Levin 定理（SAT 是 NP 完全）的证明是如何工作的。为了表明您可以将任何 NP 问题简化为 SAT，您从针对该问题的多项式时间非确定性图灵机开始，然后使用它来构建一个大量的命题公式，基本上说 "there is some computation of this TM that accepts its input string." 这在理论上很棒，但在实践中，这是一个可怕的减少，对于任何看过它的人来说几乎是完全无法理解的。任何时候你通过对一个已知的 NP 完全问题进行归约来证明问题的 NP 完全性时，都可以将其视为找到一条捷径来跳过一个非常困难的证明——如果你能找到一些简单而美好的东西，你就跳过减少的庞然大物。