@inproceedings{whittington-etal-2025-tokenisation,
    title = "Tokenisation is {NP}-Complete",
    author = "Whittington, Philip  and
      Bachmann, Gregor  and
      Pimentel, Tiago",
    editor = "Che, Wanxiang  and
      Nabende, Joyce  and
      Shutova, Ekaterina  and
      Pilehvar, Mohammad Taher",
    booktitle = "Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2025",
    address = "Vienna, Austria",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-emnlp/2025.acl-long.1365/",
    doi = "10.18653/v1/2025.acl-long.1365",
    pages = "28133--28153",
    ISBN = "979-8-89176-251-0",
    abstract = "In this work, we prove the NP-completeness of two variants of tokenisation, defined here 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)."
}