How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness

Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved {kastreva2026}. We rule out every polynomial-time M1-ε approximation, for fixed ε>0, unless P=NP, even on distinct equal-length strings with $K=m-1$. Here M is the total input length and m is the number of input strings. We complement this lower bound with a deterministic polynomial-time O(M/log M) approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets {baliga2026}; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in 2O(nloglog n/log n)(I) time, where n is the total length of the distinct input strings and I is the input encoding length. Finally, we resolve two unary merge-model hardness questions left by the bounded-alphabet study {kastreva2026}: standard unary bottom-up tokenisation is APX-hard, and unary optimal pair encoding is strongly NP-complete, strengthening the previously known weak hardness.