证明 PATH 问题不是 NP 完全问题
Proving PATH problem is not a NP-complete problem
PATH指的是图G中s到t是否存在有向路径的问题。我知道PATH∈P但是我很难证明它不是一个
NP完全问题。如果以某种方式证明了这一点，是否意味着 P≠NP？
要解决的问题 NP-complete:
- 需要NP-hard
- 它需要在 NP
要成为 NP-hard 的问题，它必须至少与 NP 中最难的问题一样难。
这意味着必须可以使用 NP-hard 问题在多项式时间内解决 NP 中的任何其他问题。
我们想证明 PATH 不是 NP-complete，但我们已经知道它在 P 中，所以它肯定也在 NP 中（平凡地，每个确定性图灵机都可以通过 non-deterministic图灵机）。
因此，要证明PATH不是NP-complete的唯一方法就是证明至少存在一个NP问题不能在多项式时间内化简为PATH。
不幸的是，你会发现这取决于P vs NP开放问题。
反证法
让我们使用旅行商问题 (TSP)，这是一个似乎与 PATH 非常相关的 NP-complete 问题。
假设 TSP 简化为 PATH，即存在 TSP 问题实例的多项式时间修改，以便它们可以由 PATH 图灵机正确求解。
我们知道所有 P 问题都可以在多项式时间内相互归约。
此外，我们知道所有 NP 问题都可以在多项式时间内简化为 TSP。
因此，通过传递性，所有 NP 问题都归结为 TSP，TSP 归结为 PATH，而 PATH 归结为所有其他 P 问题。
这产生 P = NP = NP-complete.
PATH 是一个 NP-complete 问题当且仅当 P = NP = NP-complete.
类似地，证明 PATH 不是 NP-complete 问题等同于证明 P ≠ NP ≠ NP-complete。 如果 PATH 不是一个 NP-complete 问题，则 P 中没有问题，因为所有 P 问题都可以在多项式时间内相互归约。
PATH指的是图G中s到t是否存在有向路径的问题。我知道PATH∈P但是我很难证明它不是一个 NP完全问题。如果以某种方式证明了这一点，是否意味着 P≠NP？
要解决的问题 NP-complete:
- 需要NP-hard
- 它需要在 NP
要成为 NP-hard 的问题，它必须至少与 NP 中最难的问题一样难。 这意味着必须可以使用 NP-hard 问题在多项式时间内解决 NP 中的任何其他问题。
我们想证明 PATH 不是 NP-complete，但我们已经知道它在 P 中，所以它肯定也在 NP 中（平凡地，每个确定性图灵机都可以通过 non-deterministic图灵机）。
因此，要证明PATH不是NP-complete的唯一方法就是证明至少存在一个NP问题不能在多项式时间内化简为PATH。 不幸的是，你会发现这取决于P vs NP开放问题。
反证法
让我们使用旅行商问题 (TSP)，这是一个似乎与 PATH 非常相关的 NP-complete 问题。 假设 TSP 简化为 PATH，即存在 TSP 问题实例的多项式时间修改，以便它们可以由 PATH 图灵机正确求解。
我们知道所有 P 问题都可以在多项式时间内相互归约。 此外，我们知道所有 NP 问题都可以在多项式时间内简化为 TSP。
因此，通过传递性，所有 NP 问题都归结为 TSP，TSP 归结为 PATH，而 PATH 归结为所有其他 P 问题。 这产生 P = NP = NP-complete.
PATH 是一个 NP-complete 问题当且仅当 P = NP = NP-complete.
类似地，证明 PATH 不是 NP-complete 问题等同于证明 P ≠ NP ≠ NP-complete。 如果 PATH 不是一个 NP-complete 问题，则 P 中没有问题，因为所有 P 问题都可以在多项式时间内相互归约。