Problema de Tokenización Demostrado como NP-Completo: Se Duplican los Retos de la Compresión de Datos
2024-12-22
Un artículo publicado en arXiv demuestra la completitud NP de dos variantes de la tokenización, definida como el problema de comprimir un conjunto de datos a un máximo de δ símbolos, ya sea encontrando un vocabulario directamente (tokenización directa) o seleccionando una secuencia de operaciones de fusión (tokenización ascendente). Este hallazgo tiene implicaciones significativas para la compresión de datos y el procesamiento del lenguaje natural, destacando el inmenso desafío de resolver eficientemente el problema de la tokenización para conjuntos de datos a gran escala.