计算复杂性理论 可视化实验室
用交互式 SVG 呈现 P vs NP、归约、时空复杂度、对角线化、Cook-Levin 与随机化复杂性类。八个模块，纯原生实现，可直接在浏览器中探索计算理论的核心结构。
P vs NP vs NP-Complete
复杂性类别之间的包含关系。P ⊆ NP，NP-Complete = NP ∩ NP-Hard。点击右侧问题可在关系图中定位其所属类别。
当前选中
从右侧选择一个问题，或点击图中区域查看其复杂性归属与说明。
NP 完全归约链
3SAT → Clique → VertexCover → Hamiltonian。每个 NP-Complete 问题都可归约到下一个，证明难度层层传递。播放动画观察实例的逐步变换。
归约步骤说明
点击“播放”开始归约链动画，或用“单步”逐步观察从 3SAT 公式到哈密顿回路的变换过程。
时间复杂度增长对比
从 O(1) 到 O(n!) 的增长曲线。拖动滑块改变 n，观察不同复杂度函数的相对规模。当 n 超过某阈值，指数与阶乘函数将爆炸式增长。
函数规模（n = 12）
常数与对数函数几乎水平；线性与 n log n 温和增长；多项式平稳上升；而 2ⁿ 与 n! 在 n 略大时即超出可计算范围。
空间复杂度与内存使用
不同复杂性类的内存占用可视化。L ⊆ NL ⊆ PSPACE ⊆ EXPSPACE。调整输入规模，观察各层级空间需求的增长差异。
空间层次定理
对任意可构造函数 f，SPACE(f) ⊊ SPACE(f log f)。因此严格包含关系成立，更高空间允许判定更多语言。
近似算法与近似比
TSP 最近邻近似与最优解对比，以及 Voronoi 邻近结构。PTAS / FPTAS 提供可控近似比。重新生成点集观察近似质量。
近似比 = 近似长度 / 最优长度
最近邻启发式简单快速，但最坏近似比可达 O(log n) 级别；而带三角不等式的度量 TSP 存在 1.5 近似（Christofides）。PTAS 允许任意固定 ε，FPTAS 时间关于 1/ε 为多项式。
对角线化与停机问题
图灵对角线证明：构造机器 D，使其在第 i 个输入上的行为与第 i 台机器相反，导致 D 无法出现在枚举中，从而停机问题不可判定。自指悖论。
对角线论证
假设存在能判定停机问题的图灵机 H。构造 D(x)：模拟 H(x,x)，若 H 说“停机”则 D 死循环，反之停机。问 D(D) 是否停机即导出矛盾——因此 H 不存在。
Cook-Levin 定理
3SAT 是 NP 完全的。证明分两步：① SAT ∈ NP（赋值证书可多项式验证）；② 任意 NP 问题可多项式归约到 SAT——将非确定图灵机的计算表编码为合取范式。
证明骨架
计算表是一张 T×T 的格子，每个单元格 cell[i,j] 表示时刻 i 在位置 j 的带符号/状态。用一组子句约束：合法初始格局、合法转移、接受格局可达。所有约束合取即为 SAT 实例。
随机化复杂性类
BPP / RP / ZPP 与概率图灵机。RP 允许单侧错误，BPP 允许双侧错误，ZPP 零错误期望多项式时间。关系：ZPP = RP ∩ co-RP ⊆ BPP。
概率图灵机模拟
点击“投币”模拟一次运行。RP 中 x∈L 时大部分随机串接受；x∉L 时绝不接受（单侧错误）。BPP 接受概率 >1/2，ZPP 期望时间多项式且零错误。多次重复可指数级降低错误率。