El problema dice así: se empieza con una pila de hot cakes de diferentes tamaños y la tarea es ponerlos en orden. la única restricción es que para hacer esto (innecesariamente difícil), usted no puede tocar los hot cakes con las manos. Solamente puede usar una espátula. Todo lo que puede hacerse en insertar la espátula entre dos hot cakes y voltear todos los hot cakes en conjunto, de manera que quedan en posición invertida con respecto a la posición original. (A todo esto, hay una variante a este problema: se tienen una serie de hot cakes quemados de un solo lado y hay que ponerlos todos, vía el msmo procedimiento de la espátula, con la parte quemada viendo para abajo).
La pregunta a responder es -en ambos casos- si la pila tiene N hot cakes, ¿cuál es el máximo número de giros que se necesitan como una función de n (es decir f(n))? Podemos replantear la pregunta como ¿cuál es la complejidad computacional del problema de los hot cakes?
La complejidad computacional es en realidad una rama de la teoría de la ciencia de la computación, que se enfoca en clasificar los problemas computacionales de acuerdo a su dificultad inherente. En este contexto, un problema computacional debe entender como una tarea que puede ser en principio resuelta por una computadora (lo cual significa básicamente que el problema puede ser expuesto como un conjunto de instrucciones matemáticas). Informalmente, un problema computacional consiste en instancias de problemas y las soluciones a esas instancias. Por ejemplo, el probar la primalidad de un número se basa en que el problema es sobre los números naturales y la solución a esa instancia es sí o no, de acuerdo a si el número que analizamos es primo o no.
Un problema se dice inherentemente difícil si su solución requiere recursos significativos, sin importar el tipo de algoritmo se use para resolverlo. Uno de los roles de la teoría de la complejidad computacional es determinar los límites prácticos sobre lo que las computadoras pueden o no hacer.
Hasta ahora, lo que sabemos es f(n) para n<=19 (para los hot cakes quemados, sólo sabemos para n<=17). Un equipo de tres científicos del Laboratoire d’Informatique de Nantes-Atlantique han tenido éxito en probar que el problema es del tipo NP. Para decirlo en términos sencillos, este problema es al menos tan difícil como el problema más difícil de los catalogados como NP. Y si eso no les dice nada, entonces pensemos en que lo que significa es que si se puede hallar una solución en tiempo polinomial al problema de los hot cakes, entonces de ha probado que P = NP.
Yo sé que esto suena verdaderamente ilegible, pero no lo es tanto: En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.
Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50(N^2) + N segundos, entonces el problema es resoluble en un “tiempo polinómico”. De esa manera, tiempos de 2^n+5n, es polinómicos; pero 2^n no lo es.
Pero ¿para qué sirve todo esto? el algoritmo hallado por los franceses tiene propósitos que pueden usarse prácticamente, por ejemplo en estudios genómicos. Por supuesto, en términos reales el problema de los hot cakes no tiene sentido ni aplicación real, pero sea como sea, así avanza muchas veces la ciencia.
Fuente: i-programmer
Para saber más: