有人可以请一个贴面的例子吗？如果问题处于NP中，则没有已知的多项式时间算法来解决它

Question

是否有任何已知的多项式时间算法来解决问题在NP中的问题。我被告知是错误的，但现在无法想到任何一个替换例子。

Answer 1

np是任何具有答案“是”的实例的决策问题的类，证明答案是yes，可以在多项式时间中检查。NP包含多项式时间可解决的所有问题。因此，具有已知多项式时间算法的NP中存在许多问题。

如果您谈论NP完整的问题，那就是一个完整的不同。（此时在此时）没有NP完整的问题与已知的多项式时间算法来解决它。

有人可能会发现一个证明，对于np-surfty问题，没有np-supply问题与多项式时间算法来解决它 - 不仅仅是没有已知的算法，而是根本没有算法。

另一方面，某人可能实际上可以找到可以在多项式时间中解决的NP完成。不太可能。