Anexo:Problemas no resueltos de las ciencias de la computación

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.
Other Languages