Problemas no resueltos de la informática

Los siguientes son algunos de los problemas no resueltos de las Ciencias de la Computación. Una solución de los problemas de esta lista tendría un impacto notable en el campo de estudio al que pertenecen.

Teoría de Complejidad Computacional (P versus NP)

Decidir si la inclusión entre las clases de complejidad P y NP es estricta.

Fuente:

• S. A. Cook y Leonid Levin
• Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.

Descripción: P es la clase de problemas cuya solución puede encontrarse en tiempo polinómico. NP es la clase de problemas cuya solución puede encontrarse en tiempo polinómico por una máquina de Turing no determinista (alternativamente NP es la clase de problemas cuya solución puede verificarse en tiempo polinómico por una máquina de Turing determinista). Naturalmente, cualquier problema en P también se encuentra en NP. La cuestión P versus NP es si NP está en P y si las clases son iguales. Se puede ver esta cuestión como un caso específico del problema de probar límites inferiores de costos para problemas computacionales.

Importancia: Si las clases son iguales entonces podemos resolver muchos problemas que actualmente consideramos intratables. Si no, entonces los problemas NP-completos son probablemente problemas que son NP-hard.

Conjetura actual: Aunque la pregunta está lejos de solucionarse, parece que las clases son distintas.

Criptografía

¿Existen las funciones de un solo sentido?

Fuente:

• W.Diffie, M.E.Hellman
• IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
• Copia online (HTML)

Descripción: Las funciones de un solo sentido son fáciles de calcular pero difíciles de invertir. Algunas personas conjeturan que el logaritmo discreto y la inversión RSA son funciones de un solo sentido.

Importancia: Si las funciones de un solo sentido existen, entonces la criptografía de clave pública (public key cryptography) es posible. Su existencia implicaría que P no es NP.

Conjetura actual: Está asumido pero no probado que existen.

Informática de alto rendimiento

¿Hasta qué grado se puede aumentar la velocidad de la computación?

Fuente:

Descripción: Aunque el teorema del aumento de velocidad de la teoría de computación indica que cualquier computación puede acelerarse por una constante, no hay método de ganar dicha mejora de velocidad. Se necesita saber cuáles son las técnicas y límite en varias arquitecturas.

Importancia: La velocidad de computación es el límite a los problemas que podemos resolver.

Conjetura actual: La Ley de Amdahl es una solución parcial al problema.

¿Cómo se puede construir un Cluster de computadores de N nodos?

Fuente:

Descripción: Mientras que el número de ordenadores en un cluster aumenta, la probabilidad de fallo en uno de estos también aumenta. En un punto, la media de tiempo entre fallos es menor que los tiempos de recuperación y comprobación. ¿Es posible de alguna forma que el aumento de la probabilidad de fallo limite la tasa de incremento de potencia?

Importancia: Los clusters son un método poderoso de ganar potencia de computación. Así, las limitaciones del tamaño del cluster también lo son de la potencia de cálculo.

Conjetura actual:

Encontrar un algoritmo de planificación optimo de UET para 3 procesadores con restricciones de precedencia

Fuente:

• Marc Chardon, Aziz Moukrim
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders, SIAM J. Discrete Math, Volume 19 (2005), Number 1 pp. 109-121.

Descripción: Un problema de planificación de unit-execution-time (UET) contiene tareas todas ellas de igual longitud. Cuando hay restricciones de precedencia entre las tareas, entonces significa que existe un grafo dirigido entre las tareas UET. Para comenzar una tarea todas sus predecesoras deben haber acabado. Dos algoritmos optimos se conocen para tareas UET de 2 procesadores. [CoffmanGraham72] [GareyJohnson76].

Importancia: Este problema es equivalente a planificar instrucciones en una computadora superscalar y planificar tareas paralelas de forma optima en un multiprocesador con 3 procesadores.

Conjetura actual:

Véase también

• Problemas no resueltos de la matemática
• Problemas no resueltos de la ingeniería de software