Por @Alvy — 15 de Enero de 2023

El zoo de la complejidad, un curioso lugar sobre la complejidad matemática

El Zoo de Complejidad (Complexity Zoo) es una herramienta de referencia para teóricos de la informática y estudiantes, pero también puede venir bien a programadores, matemáticos, físicos y curiosos que se encuentre ocasionalmente con el concepto «clases de complejidad».

Quién más quien menos habrá oído algo sobre el problema ¿P = NP?, que viene a preguntar si las clases de complejidad P y NP son equivalentes o no. Esto tiene que ver con las formas de catalogar la dificultad intrínseca de los problemas o algoritmos, por ejemplo el problema del viajante, un algoritmo de ordenación u otro para resolver sudokus.

En este ejemplo P es la clase llamada «tiempo polinomial» y NP es «tiempo polinomial no determinista», que se sabe contiene a P pero no está claro que sean exactamente iguales (es una de las cuestiones matemáticas abiertas todavía sin solución). Pues bien, además de P y NP –que son de las más conocidas– hay cientos de otras clases de complejidad con nombres tan curiosos como para-NL (espacio logarítmico no determinístico parametrizado) o PEXP (tiempo exponencial probabilístico).

El zoológico tiene una lista a día de hoy de 546 clases de complejidad, muchas de las cuales tienen que ver con la información cuántica. Funciona como un wiki y tiene un «cuidador», que no es ni más ni menos que nuestro admirado Scott Aaronson, con Greg Kuperberg como «veterinario» y Oliver Habryka como «conservador», representando a la comunidad de LessWrong. Se actualiza de vez en cuando, tanto con clases de complejidad conocidas como desconocidas, siempre y cuando algo se haya dicho algo sobre ellas que no sea trivial.

Bonus: un buen artículo sobre el estado de la cuestión P = NP es este que publicaron en Communications of the ACM el año pasado: Fifty Years of P vs. NP and the Possibility of the Impossible.

Relacionado:

Compartir en Flipboard Publicar / Tuitear