P与NP澄清

Question

从维基百科引述的P vs NP问题，关于算法的时间复杂性，“……询问是否每个其解决方案可以被计算机快速验证的问题也可以被计算机快速解决。”

我希望有人能澄清一下，“验证问题”和“解决问题”的区别在这里。

Answer 1

RSA使用如下的质数:两个大质数P和Q(每个200-400位)被相乘以形成公钥N。N=P*Q要破解加密，人们需要在给定N的情况下计算出P和Q。虽然找到P和Q非常困难，并且可能需要数年时间，但验证解决方案只是将P乘以Q并与N进行比较。因此，解决问题非常困难，而不需要验证解决方案。

附注:此示例仅是此问题的RSA简化版的一部分。真正的RSA要复杂得多。