二进制分词问题被证明近似难解，并给出双标准近似算法
热点事件持续更新
二进制分词问题被证明近似难解，并给出双标准近似算法
1 篇报道1 个报道来源3 小时前更新
先了解这件事
AI 综述
Atieh Bastan、Xiaoling He、A. Pavan、N. V. Vinodchandran 在 arXiv 论文《Tokenization: Hardness and Bicriteria Approximation Algorithms》中研究二进制分词问题：给定二进制语料和词表预算 K，选出至多 K 个子串以最小化表示语料所需 token 总数。论文证明，对任意固定 ε∈(0,1)，在 P≠NP 假设下该问题不存在多项式时间 n^{1-ε} 近似算法。 作为难解性结果的补充，论文给出多项式时间的 (γ,γ) 双标准近似算法，其中 γ=√M·log n：输出词表不超过 γK，且 token 数不超过最优解 γOPT_K。
AI 根据报道生成 · 2 小时前更新
最新进展11月14日 13:00
二进制分词的难解性与双标准近似算法报道时间线
沿着报道，了解事件的不同侧面。
11月14日
- arXiv cs.AI二进制分词的难解性与双标准近似算法
一篇 arXiv 论文研究二进制分词问题：给定二进制语料和词表预算 K，选出至多 K 个子串以最小化表示语料所需 token 总数。论文证明对任意固定 ε∈(0,1)，该问题在 P≠NP 假设下不存在多项式时间 n^{1-ε} 近似算法，并给出 (γ,γ) 双标准近似算法，γ=√M·log n，输出词表不超过 γK、token 数不超过 γOPT_K。
本事件热度走势
还没有足够的连续观测数据，暂不绘制趋势。