我们怎么知道 NP 完全问题是 NP 中最难的？
How do we know NP-complete problems are the hardest in NP?
我知道如果你可以从 "every" 问题中减少多项式时间那么它证明这个问题至少和 NP 中的每个问题一样难。除了，我们怎么知道我们已经发现了 NP 中的每个问题？难道不能存在我们可能没有发现或证明存在于 NP 中但不能简化为任何 np-complete 问题的问题吗？或者这仍然是一个悬而未决的问题？
NP 包含所有（理论上）可以通过幸运猜测、猜测解决方案并在多项式时间内检查解决方案是否正确来解决的问题。例如，旅行商问题 "can I visit the capitols of all 50 states of the USA with a trip of less than 9,825 miles" 可以通过猜测一次旅行并检查它是否不太长来解决。
而NP中的一个问题基本上是模拟具有各种输入的可编程计算机电路并检查是否可以实现某种输出。那个可编程的计算机电路足够强大，可以解决 NP 中的所有问题。
所以是的，我们知道 NP 中的所有问题。
(那么一个NP完全问题当然可以根据定义用来解决NP中的任何问题。如果有一个它不能解决的问题，那个问题不在NP).
Except, how do we know that we've discovered every problem in NP?
我们没有。宇宙中所有问题的集合不仅是无限的，而且是不可数的。
Can't there exist problems that we may not have discovered or proven
exist in NP but CANNOT be reduced to any np-complete problem?
我们不知道。我们怀疑是这种情况，但这尚未得到证实。如果我们要找到一个不在 NP-Complete 中的 NP 问题，这将证明 P =/= NP。
这是CS中未解决的重大问题之一。许多聪明才智一直在尝试，但这个坚果很难破解。
正如其他人正确指出的那样，存在 NP 但不是 NP 完全的问题意味着 P != NP，因此找到一个会给你带来 million dollar and eternal glory. One famous problem that is believed to belong in this class is integer factorization。但是，您最初的问题是
Can't there exist problems that we may not have discovered or proven
exist in NP but CANNOT be reduced to any np-complete problem?
答案是否。根据 NP-completeness 的定义，两者之一
问题 A 成为 NP-complete 的必要条件是每个 NP 问题都需要在多项式时间内简化为 A。如果您想了解如何证明每个 NP 问题都可以在多项式时间内简化为某些 NP-完整的问题，请查看 Cook-Levin theorem 的证明，该证明表明 3-SAT 问题是 NP 完全问题。这是第一个被证明的 NP 完全问题，许多其他 NP 完全问题后来通过找到从 3-SAT 到这些问题的适当减少被证明是 NP 完全问题。
我知道如果你可以从 "every" 问题中减少多项式时间那么它证明这个问题至少和 NP 中的每个问题一样难。除了，我们怎么知道我们已经发现了 NP 中的每个问题？难道不能存在我们可能没有发现或证明存在于 NP 中但不能简化为任何 np-complete 问题的问题吗？或者这仍然是一个悬而未决的问题？
NP 包含所有（理论上）可以通过幸运猜测、猜测解决方案并在多项式时间内检查解决方案是否正确来解决的问题。例如，旅行商问题 "can I visit the capitols of all 50 states of the USA with a trip of less than 9,825 miles" 可以通过猜测一次旅行并检查它是否不太长来解决。
而NP中的一个问题基本上是模拟具有各种输入的可编程计算机电路并检查是否可以实现某种输出。那个可编程的计算机电路足够强大，可以解决 NP 中的所有问题。
所以是的，我们知道 NP 中的所有问题。
(那么一个NP完全问题当然可以根据定义用来解决NP中的任何问题。如果有一个它不能解决的问题，那个问题不在NP).
Except, how do we know that we've discovered every problem in NP?
我们没有。宇宙中所有问题的集合不仅是无限的，而且是不可数的。
Can't there exist problems that we may not have discovered or proven exist in NP but CANNOT be reduced to any np-complete problem?
我们不知道。我们怀疑是这种情况，但这尚未得到证实。如果我们要找到一个不在 NP-Complete 中的 NP 问题，这将证明 P =/= NP。
这是CS中未解决的重大问题之一。许多聪明才智一直在尝试，但这个坚果很难破解。
正如其他人正确指出的那样，存在 NP 但不是 NP 完全的问题意味着 P != NP，因此找到一个会给你带来 million dollar and eternal glory. One famous problem that is believed to belong in this class is integer factorization。但是，您最初的问题是
Can't there exist problems that we may not have discovered or proven exist in NP but CANNOT be reduced to any np-complete problem?
答案是否。根据 NP-completeness 的定义，两者之一 问题 A 成为 NP-complete 的必要条件是每个 NP 问题都需要在多项式时间内简化为 A。如果您想了解如何证明每个 NP 问题都可以在多项式时间内简化为某些 NP-完整的问题，请查看 Cook-Levin theorem 的证明，该证明表明 3-SAT 问题是 NP 完全问题。这是第一个被证明的 NP 完全问题，许多其他 NP 完全问题后来通过找到从 3-SAT 到这些问题的适当减少被证明是 NP 完全问题。