Tokenisation is NP-Complete
classification
💻 cs.DS
cs.CLcs.FL
keywords
tokenisationbottom-upcompressingdatasetdefineddeltadirectdirectly
read the original abstract
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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.