Hola a todos!
Tiene ya casi un año que tengo esta publicación entre mis borradores; que diversas circunstancias, he dejado junto con otras que he publicado últimamente o estoy en proceso de publicar.
Este post, tiene tanto un objetivo divulgativo como un objetivo divertido y tiene mucho que ver con uno de los últimos posts sobre complejidad, donde explico qué es a muy grandes rasgos y cuál es su utilidad. Aquí les dejo un enlace; ya que si no conoces lo que es la complejidad computacional, podría ser difícil entender este post.
Bien, con eso aclarado, continuemos a la parte informativa.
Como sabemos; existen problemas que «no podemos resolver» sin usar algo que se conoce como el No Determinismo. Justo como con la mayoría de algoritmos (y programas) que conocemos y a los que estamos acostumbrados, podemos calcular su tiempo de ejecución y acotarlo usando alguna función matemática. Comentaba sobre NP – algoritmos no deterministas con tiempo de ejecución polinomial (queda acotado por un polinomio de algún grado).
Pues resulta que la universidad de Cornell (NY, EE UU) publicó un artículo en 2015 donde se hace un estudio que concluye en que:
Los títulos de videojuegos de franquicias de Nintendo como Super Mario, The Legend of Zelda, Donkey Kong, Metroid y Pokémon; representan problemas NP-difíciles.
En la jerga gamer, se le suele llamar Nintendo-hard a los videojuegos que son difíciles; mucho muy difíciles, indiferentemente que hayan sido producidos y/o publicados por Nintendo. Esto en referencia a que los juegos clásicos de Nintendo (como los del estudio), son muy muy difíciles.
Además, consideremos que cualquier problema NP puede ser convertido en una instancia de otro problema NP-díficil; es decir, los problemas NP-difíciles pueden resolver otros problemas NP (usando alguna transformación del problema NP original). Así entonces,
Podemos decir que ya que los juegos clásicos de Nintendo (al menos los del estudio) representan problemas NP-díficiles y además son Nintnedo-hard; entonces los problemas NP-hard o NP-díficiles, son también problemas computacionalmente Nintendo-hard o Nintendo-difíciles.
Así, ya sea que P = NP o no; al menos NP-hard = Nintendo-hard.
Y así, el artículo con más facha académica en este blog, es también uno de los más nerdos.
Referencias.
- Aloupis, G.; Demaine, E. D.; Guo, A.; Viglietta, G., (2015), «Classic Nintendo Game are (computationally) Hard» en Cornell University Library. [En línea]. EE UU, disponible en: https://arxiv.org/abs/1203.1895 [Accesado el día 17 de octubre del 2016].
- Arora, S. y Barak, B., (2007), «Computational complexity: a modern aproach», Cambridge University Press.
Nachintoch 