NP 问题与非确定性算法：猜测再验证

旅行商问题（在预算里走完所有城市）目前没有已知的多项式时间确定性解法，但存在一个取巧的”非确定性算法”：先凭空”猜”一条路径（这一步不说明怎么选，只假设机制足够聪明能直接选中），再验证这条路径总长度是否达标——猜测这一步不需要真正搜索，验证这一步复杂度也只是多项式级别。凡是能用这种”猜一个候选解、再多项式时间验证”的方式解决的问题，称为非确定性多项式问题，简称 NP 问题。P 类问题必然也是 NP 问题（确定性算法本身就能当作”猜得每次都对”的非确定性算法），但反过来 NP 问题是否都属于 P，是计算机科学最著名的未解难题——大多数人相信答案是否定的，但至今没人能证明。发散：非确定性算法的”猜测”步骤，本质上是把”找到解有多难”这件事从算法复杂性分析里挖掉，只保留”验证一个候选解有多难”——这提醒我们”找解”和”验解”可能是难度完全不对称的两件事，这个不对称性正是[[RSA 公钥加密：利用计算不对称性构建的加密系统|RSA 公钥加密]]赖以安身立命的根基。