Tokenisation is NP-Complete

Philip Whittington; Gregor Bachmann; Tiago Pimentel

doi:10.18653/v1/2025.acl-long.1365

ACL2025顶会

Tokenisation is NP-Complete

Philip Whittington, Gregor Bachmann, Tiago Pimentel

arXiv DOI 出版方

2025年份

6被引次数

3顶会引用

摘要

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