5.3.2 P 内部问题的条件下界（如 3SUM 问题）

文档摘要

5.3.2 P 内部问题的条件下界（如 3SUM 问题） 5.3.2 P 内部问题的条件下界（如 3SUM 问题）想象一下，你手握一堆整数，任务简单却狡猾：从中挑出三个，让它们的和恰好为零。这就是3SUM问题，看似儿戏，却像一枚隐藏在计算理论深处的地雷，炸出了细粒度复杂性领域的惊人洞见。在P类问题中，我们早已习惯多项式时间解法，但3SUM提醒我们：并非所有多项式都生而平等。有些问题顽强地守着$n^2$门槛，拒绝任何显著加速。这不是巧合，而是通过条件下界（Conditional Lower Bounds）铸就的铁律。本节，我们不只停留在“为什么”，更直奔“怎么做”——从算法实现，到界限证明的核心技巧，再到实战中的陷阱与优化，一步步拆解，让你能亲手编码、验证，甚至挑战这些界限。