我知道，如果你可以对“每个”问题进行多项式时间缩减，那么就证明这个问题至少与 NP 中的每个问题一样难。除了，我们怎么知道我们已经发现了 NP 中的所有问题？难道不能存在我们尚未发现或证明存在于 NP 中但不能简化为任何 np 完全问题的问题吗？或者这仍然是一个悬而未决的问题？
最佳答案
正如其他人正确指出的那样，存在 NP 但不是 NP 完全的问题意味着 P != NP，因此找到一个会给你带来 million dollar和永恒的荣耀。一个被认为属于此类的著名问题是 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 完整性的定义，两个之一 问题 A 是 NP 完全的必要条件是每个 NP 问题都需要在多项式时间内可简化为 A。如果你想找出如何证明每个 NP 问题都可以在多项式时间内简化为某个 NP-完整的问题，看一下Cook-Levin theorem的证明表明 3-SAT 问题是 NP 完全问题。这是第一个被证明的 NP 完全问题，后来通过找到从 3-SAT 到这些问题的适当约简，许多其他 NP 完全问题被证明是 NP 完全问题。
关于big-o - 我们怎么知道 NP 完全问题是 NP 中最难的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37553577/