如果p= np，则在多项式时间运行的算法

Question

上wikipedia ，它说有一些算法会运行在多项式时间，如果且仅当p= np时。他们给了一个例子（没有引文），但还有其他人吗？我试图看着它们，找不到任何东西。

Answer 1

维基百科正在描述Levin的通用算法。这是一种可验证问题的算法，它与最佳算法（某种意义）具有竞争力。特别是，完全相同的方法将在NP中为任何问题工作，而不仅仅是子集合。