指数时间假设 ETH

P 与 NP理路复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 问题只问是否存在某个多项式时间算法；ETH 进一步猜测 SAT 的指数部分不能压缩到次指数。它为“困难到什么量级”提供刻度：一个归约若把 SAT 的 $n$ 个变量变成目标问题的参数 $k=O(n)$，目标上的 $2^{o(k)}$ 算法就会反推出被 ETH 排除的 3-SAT 算法。

这个假设不指定最佳指数底数，也不声称所有 NP 困难问题都恰需 $2^n$。它只保留一个正的指数常数下界，让归约能够排除次指数依赖。

穷举全部布尔赋值在 $O^{\ast }(2^n)$ 时间内求解 3-SAT，与 ETH 完全相容；即使发现 $O^{\ast }({1.3}^n)$ 算法，也仍是 $2^{\mathrm{\Theta }(n)}$，不会否定假设。相反，$2^{\sqrt{n}}\mathrm{poly}(|\phi |)$ 或 $n^{\log n}$ 都是 $2^{o(n)}$，若能解决所有 3-SAT 实例便会直接推翻 ETH。

这一区分展示的不是“把 2 换成 1.3”的伪例，而是指数级与次指数级的边界：前者仍有线性指数，后者的指数除以 $n$ 后趋于零。条件下界必须证明目标算法会跨过这条边界，而不能只说它“比暴力快”。

若以公式总长度 $N$ 计，变量很少但含大量重复子句的输入会使 $2^{o(N)}$ 与 $2^{o(n)}$ 表达不同主张。把 3-SAT 改成 2-SAT 也不成立，因为 2-SAT 有多项式时间算法。ETH 更不排除 $2^{0.01n}$；它断言的是某个正指数常数不可消失，而非常数至少等于 $1$。

ETH 通过规模保持归约给图算法、参数化算法和精确算法提供条件下界，例如排除某些 $2^{o(k)}$ 或 $n^{o(k)}$ 时间形式。每条结论都要核对归约后的规模关系：若目标参数增长为 $k=\mathrm{\Theta }(n^2)$，一个 $2^{o(k)}$ 算法未必转化成 $2^{o(n)}$，不能只凭“大 O”口号传递假设。

SETH理路强指数时间假设 SETHStrong Exponential Time Hypothesis · SETH假设随着子句宽度增长，k-SAT 的最优指数底数不能被某个统一小于 2 的常数界定。会约束所有固定宽度 $k$-SAT 的最佳指数率，并在 $k$ 增大时逼近穷举指数 $1$；它蕴含 ETH，但反向仍未知，二者不能互称等价。ETH 页面只建立 3-SAT 的次指数禁区，并为后续稀疏化、SETH 与细粒度归约提供明确基线。

Petri 覆盖性复杂度理路Petri 网覆盖性的复杂度Petri net coverability complexity · Rackoff bound说明普通无界 P/T 网覆盖性为何 EXPSPACE 完全，区分见证长度、存储位数和具体算法的最坏表现。区分经典的 EXPSPACE 完全性与进一步的参数化、条件最优界。这里的经典上下界不依赖 ETH；若引用按维数或运行长度细化的条件下界，仍应保留其编码和复杂度假设，不能混作同一结论。