Problema de Tokenização Provado como NP-Completo, Dobrando os Desafios de Compressão de Dados
2024-12-22
Um artigo publicado no arXiv prova a completude NP de duas variantes de tokenização, definida como o problema de comprimir um conjunto de dados para no máximo δ símbolos, encontrando um vocabulário diretamente (tokenização direta) ou selecionando uma sequência de operações de mesclagem (tokenização bottom-up). Essa descoberta tem implicações significativas para a compressão de dados e o processamento de linguagem natural, destacando o imenso desafio de resolver eficientemente o problema de tokenização para conjuntos de dados em larga escala.