三七二十一
LUCKY !

问题陈述

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加密等将不再安全。

返回