P 对 NP 问题
所有可在多项式时间内验证的问题是否也能在多项式时间内求解，即 P 是否等于 NP。
详细描述
P 类是所有能由确定型图灵机在多项式时间内求解的判定问题；NP 类是那些”肯定答案可在给定证书后于多项式时间内验证”的判定问题，等价于可在非确定型图灵机上多项式时间内求解。显然 ，P 对 NP 问题即问是否 。
1971 年，Stephen Cook 在论文《定理证明过程的复杂性》中严格提出此问题，并证明布尔可满足性（SAT）是 NP 完全问题——任何 NP 问题都能在多项式时间内归约到它。其后 Leonid Levin 独立给出类似结果。若任一 NP 完全问题属于 P，则所有 NP 问题都属于 P。
最新进展
学界主流倾向于 ：2002 年对百位研究者的调查中，约 61 人相信答案是否定的。尽管大量问题（如旅行商、整数规划、图谱着色）被证明 NP 完全，且多项式时间算法长期缺位，但严格的分离证明至今缺席。P 对 NP 是七大千禧年难题之一（与黎曼、庞加莱[已解]、霍奇、杨-米尔斯、纳维–斯托克斯、BSD 并列），克雷数学研究所悬赏百万美元。
意义
现代公钥密码学（RSA、椭圆曲线）的安全性正建立在”某些问题易验证而难求解”的假设之上。若 被证明，现有多数加密体系将崩溃，同时使证明搜索、药物设计、调度优化等可获高效算法；若证得 ，则确立计算的内在局限。