计算复杂性理论中的P与NP问题 计算复杂性理论是研究计算问题所需资源（如时间、空间）的理论。P与NP问题是该领域的核心开放问题，涉及问题可解性与可验证性的本质差异。 1. 基本概念：判定问题与计算模型 判定问题是指答案为"是"或"否"的问题，例如"给定整数n是否为素数" 图灵机是研究计算复杂性的标准计算模型，分为确定性图灵机（DTM）和非确定性图灵机（NTM） DTM每个计算步骤只有一种可能选择，而NTM每个步骤可以有多种选择并行探索 2. 时间复杂度与复杂度类P 时间复杂度描述算法运行时间随输入规模增长的变化趋势 多项式时间：运行时间上界为输入规模的多项式函数，如O(n²) 复杂度类P：所有能被确定性图灵机在多项式时间内解决的判定问题的集合 例子：排序问题、最短路径问题都属于P类 3. 非确定性计算与复杂度类NP NP是非确定性多项式时间的缩写，指能被非确定性图灵机在多项式时间内解决的判定问题集合 等价定义：如果问题的解能在多项式时间内被验证，则该问题属于NP 例子：布尔可满足性问题（SAT）——给定布尔公式，是否存在变量赋值使其为真 4. NP完全性问题 多项式时间归约：问题A可归约为问题B，意味着A的实例能在多项式时间内转化为B的实例 NP完全问题：满足两个条件：(1)属于NP类；(2)NP中所有问题都可多项式归约到该问题 Cook-Levin定理证明了SAT问题是第一个被发现的NP完全问题 其他NP完全问题包括旅行商问题、图着色问题等 5. P与NP关系的核心问题 P ⊆ NP是已知的（确定性计算是非确定性计算的特例） 开放问题：NP ⊆ P是否成立？即P = NP吗？ 如果P = NP，意味着所有容易验证的问题都容易解决 该问题被克莱数学研究所列为七大千禧年难题之一 6. 当前研究进展与扩展 多项式层次结构：推广P和NP概念形成的复杂度类层次 近似算法：对于NP难问题，研究在多项式时间内找到近似解的算法 平均复杂度：研究问题在随机输入实例下的期望复杂度 电路复杂性：从布尔电路角度研究计算复杂性 理解P与NP问题有助于认识计算问题的内在难度，对密码学、优化算法等领域有深远影响。