二元分词问题被证无高效近似算法
热点事件观察中
二元分词问题被证无高效近似算法
1 篇报道1 个报道来源1 天前更新
先了解这件事
AI 综述
Atieh Bastan 等作者发表论文，研究二元分词（Binary Tokenization）问题的计算难度：给定二进制字符串语料和词表预算 K，需选出至多 K 个子串作为词表，使表示语料所需 token 总数最少。作者证明该问题不存在多项式时间的 n^{1-ε} 近似算法，除非 P=NP。 作为应对，作者提出多项式时间的 (γ,γ) 双标准近似算法，γ=√M·log n，输出词表规模不超过 γK、token 数不超过 γ·OPT_K；存储预算变体在 2≤B<n 时获得 (O(log n log B), O(log n log B)) 双标准近似。
AI 根据报道生成 · 10 小时前更新
最新进展11月14日 13:00
二元分词问题的计算难度与双标准近似算法报道时间线
沿着报道，了解事件的不同侧面。
11月14日
- arXiv cs.AI二元分词问题的计算难度与双标准近似算法
研究证明二元分词（Binary Tokenization）问题不存在多项式时间的 n^{1-ε} 近似算法，除非 P=NP。为此提出多项式时间的 (γ,γ) 双标准近似算法，γ=√M·log n，输出词表规模不超过 γK、token 数不超过 γ·OPT_K；存储预算变体在 2≤B<n 时获得 (O(log n log B), O(log n log B)) 双标准近似。
本事件热度走势
- 可比范围当前
- 5
- 可比范围峰值
- 711月15日 04:00
- 近 24 小时变化
- –
02468
04:0006:0008:0010:0012:00
趋势仅比较持续完整观测到的相同主体，范围可能小于当前热度统计。移动指针或点击图表查看每小时热度；键盘可用左右方向键切换。