证明了两种分词方法的计算复杂性为NP完全。

Tokenisation is NP-Complete

• 将分词建模为符号压缩问题，分为直接找词表和自底向上合并两种形式。
• 在任意给定符号上限δ时，两类分词问题均属于NP完全。
• 对分词算法设计有理论指导意义，适合研究者阅读。

本文证明了两种分词变体的NP完全性：一种是直接寻找词表以将数据集压缩至最多δ个符号（直接分词）；另一种是通过选择一系列合并操作实现压缩（自底向上分词）。这两个问题在给定符号数量上限δ时均属于NP完全，表明不存在高效求解的通用算法，揭示了分词任务的内在计算难度。

原文摘要 · Abstract (English)

In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most $δ$ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。