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:
The Golden Ticket: un libro divulgativo sobre la cuestión P = NP
Comprobar si p es primo está realmente en P
Avances y mejoras tras 44 años en el problema matemático del viajante
Deja tu comentario