TCzajka 科普 3-SAT 亚指数时间结果中的「指数时间」歧义

理论计算机科学家 TCzajka 科普 3-SAT 亚指数时间新结果，区分「指数时间」的两种复杂度含义。类 E 指 2^O(n)，即 O(c^n)；EXPTIME 则涵盖 O(2^(n^k))，所有 NP 问题都在其中。亚指数时间亦有 2^o(n) 定义，即对每个 ε>0 为 O(2^(εn))，不同定义会改变结论强度。