主要来源arXiv: OpenAI
查看原文事件专题 ·官方一手
Exact-One Hitting Set 问题获得亚指数时间精确计数算法
Exact-One Hitting Set 是 Karp 最早提出的 21 个 NP 完全问题之一。作者将归约与 OpenAI 2026 年的固定宽度精确计数定理结合，得到一个确定性多项式空间算法，可在 2^{O(r log log(r+16)/√log(r+16))} poly(L+1) 即 2^{o(r)} poly(L+1) 时间内精确计算可行选择数量，其中 r 为基集大小、L 为输入长度。论文还用双查询计数消抵的路径表示，构造两个至多 2r 个变量、O(r^2) 子句的 3-CNF 公式，使模型计数之差等于目标答案，并扩展到带符号方程和 VC 维至多一的布尔关系。
当前结论
arXiv 上一篇理论论文，把 Karp 的老牌 NP 完全问题 Exact-One Hitting Set 做到了 2^{o(r)} 时间，算法理论圈可以看看。
3 个信源19° AI 热度最后更新 2026/10/31 14:32:34
证据链
3 个信源冲突核查
现有去重数据只说明这些来源讨论同一事件，不代表立场相同。当前没有结构化的支持或反驳证据，不自动推断冲突。