A primera vista, la gran noticia surgida de la conferencia de este verano sobre la teoría de la computación parecía ser algo decepcionante. Durante más de 40 años, los investigadores habían tratado de encontrar una forma mejor de comparar dos cadenas arbitrarias de caracteres, como las largas cadenas de letras químicas que contienen las moléculas de ADN. El algoritmo más utilizado es lento y no especialmente ingenioso: avanza paso a paso por las dos listas, comparando valores en cada paso. Si se encontrara un método mejor para calcular esta “distancia de edición”, los investigadores podrían comparar con rapidez genomas completos o grandes conjuntos de datos, y los informáticos dispondrían de una nueva y poderosa herramienta con la que intentar resolver problemas adicionales en el campo.
Sin embargo, en un artículo presentado en el ACM Symposium on Theory of Computing, dos investigadores del Massachusetts Institute of Technology presentaron una demostración matemática de que el mejor algoritmo actual era “óptimo” —es decir, que encontrar una forma más eficiente de calcular la distancia de edición era matemáticamente imposible. The Boston Globe celebró el logro de los investigadores locales con un titular que decía “Durante 40 años, los científicos de la computación buscaron una solución que no existe.”
Pero los investigadores aún no están preparados para registrar la hora de la muerte. Sigue existiendo una laguna importante. El resultado de imposibilidad solo es verdadero si también lo es otra afirmación, famosamente no demostrada, llamada hipótesis fuerte del tiempo exponencial (SETH). La mayoría de los investigadores de complejidad computacional asume que así es, incluidos Piotr Indyk y Artūrs Bačkurs del MIT, quienes publicaron el hallazgo sobre la distancia de edición, pero la validez de SETH sigue siendo una cuestión abierta. Esto hace que el artículo sobre el problema de la distancia de edición parezca una versión matemática del célebre informe sobre la muerte de Mark Twain: muy exagerado.
La confusión de los medios de comunicación sobre la distancia de edición refleja una falta de claridad en las profundidades de la teoría de la complejidad en sí misma, donde matemáticos e informáticos intentan delimitar qué es y qué no es factible de calcular , como si fueran exploradores de las profundidades marinas que trazan el fondo de una fosa oceánica. Este terreno algorítmico es tan vasto —y tan mal comprendido— como el verdadero lecho marino, afirmó Russell Impagliazzo, un teórico de la complejidad que formuló por primera vez la hipótesis del tiempo exponencial junto con Ramamohan Paturi en 1999. “La analogía es buena —dijo él—. Los océanos son donde reside la dureza computacional. Lo que intentamos hacer es usar herramientas más finas para medir la profundidad del océano en distintos lugares.”
Para seguir leyendo, visite Quanta Magazine. La publicación no implica que el Foro Económico Mundial respalde las opiniones expresadas.
Para estar al día con la Agenda, suscríbase a nuestro boletín semanal.
Autor: John Pavlus es escritor y cineasta cuyo trabajo ha aparecido en Scientific American, Bloomberg Businessweek y en la serie The Best American Science and Nature Writing.
Imagen: Una ilustración muestra una proyección de código binario sobre un hombre que sostiene un ordenador portátil, en una oficina de Varsovia. REUTERS/Kacper Pempel
