NP 到 P 转换

Question

是否有任何最近（也可以随意添加 "old" 个）问题被认为是 NP，后来有人提出了多项式的解决方案？我认为研究这些案例将有助于培养解决关键问题的诀窍以及练习竞争性编程。

Answer 1

其中一个问题是确定给定整数是否为素数。 PRIMES IS IN P 是 2002 年发布这一消息的著名论文，几乎出乎所有人的意料。 我想你会发现这个 link 很有帮助。