5.3.1 强指数时间假设（SETH）

文档摘要

5.3.1 强指数时间假设（SETH） 5.3.1 强指数时间假设（SETH）想象一下，你正站在计算理论的悬崖边上，下面是指数时间的深渊。传统复杂性理论告诉我们，某些问题注定逃不掉这个深渊，但细粒度复杂性——尤其是强指数时间假设（SETH）——则像一把精密的量尺，精确丈量这个深渊的深度。它不满足于粗略的“NP-hard就完事了”，而是追问：$k$-SAT问题真的能在$2^{n(1-\epsilon)}$时间内解决吗？答案是“很可能不能”，而这个“很可能”支撑起无数算法的下界证明。作为一名深耕细粒度复杂性的一线研究员，我见过太多算法在SETH的铁壁前折戟，也亲手构建过那些用来验证和挑战它的实验框架。