指数时间猜想与推理复杂度：3-SAT 难解性对 AI 推理意味着什么

指数时间猜想（ETH）若成立，3-SAT 等布尔方程无法快于指数时间 O(e^{cn}) 求解，其是否被推翻将直接影响 AI 推理复杂度判断。但即便该猜想被推翻，也只意味着部分布尔推理可能比预想更容易，不代表 AI 推理成本会显著下降。