问题陈述
P类:可在多项式时间内求解。NP类:解可在多项式时间内验证。P=NP? 如果解可快速验证,是否一定可快速求解?千禧年难题。
If a solution can be verified quickly, can it always be found quickly?NP-完全问题
旅行商问题、SAT、背包问题都是 NP-完全的。如果任一被证明属于P,则 P=NP,将颠覆加密学。
TSP, SAT, Knapsack are NP-complete.影响
如果 P≠NP(多数计算机科学家相信),某些问题本质上比另一些难。如果 P=NP,RSA加密等将不再安全。