arXiv · AI· Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran·· 7 天前AI 评分27
Tokenization 问题的计算复杂性证明及双指标近似算法
Tokenization: Hardness and Bicriteria Approximation Algorithms
AI 导读
论文证明 Binary Tokenization 问题在 P≠NP 假设下不存在多项式时间 n^{1-ε}-近似算法。 提出多项式时间 (γ,γ)-双指标算法,其中 γ = √M log n,输出词表大小与 token 数均不超过 γ 倍最优值。
来源:arXiv · AI · arxiv.org