4.3.1 计算时间资源：P/NP/BPP/EXP类在时间维度上的分离本质

文档摘要

4.3.1 计算时间资源：P/NP/BPP/EXP类在时间维度上的分离本质我们常把“P vs NP”问题比作计算理论的珠穆朗玛峰——人人都知道它高，却少有人真正攀过它的北坡，更少有人在海拔5000米处校准自己的氧气阀、检查冻伤指节、调试那台在-30℃仍要稳定运行的SAT求解器。今天，我们不谈哲学隐喻，不列教科书定义，不复述Cook定理的证明草稿。我们钻进编译器后端的时序分析器里，蹲在CPU流水线发射窗口前，亲手构造一个能在$2^{n/10}$内判定3-SAT实例的C++实现，再把它拉进gprof火焰图里看哪一行代码在啃食时间资源；我们调参BPP类算法的随机种子生成器，观察当换成时，错误率如何从$1/4$滑向$1/2^8$；