¿Es P no igual a NP?
Un investigador dice haber demostrado que los problemas tipo NP no pueden ser equivalentes a problemas tipo P.
|
¿Ha sido resuelto uno de los grandes enigmas de la computación? ¿Es todo problema de tipo NP igual a uno de tipo P? Según un investigador la respuesta es no.
La relación entre las clases de complejidad P y NP es estudiada por la teoría de la complejidad computacional que trata de los recursos (tiempo o memoria) requeridos durante un cálculo para resolver un problema dado. En esta teoría, la clase P contiene aquellos problemas de decisión que pueden ser resueltos con una máquina determinista secuencial (un ordenador) en un período de tiempo polinómico que es proporcional a los datos de entrada. Es decir, que si aumentamos los datos de entrada, el tiempo necesario para resolverlo no crece exponencialmente, sino más ñentamente. Este tipo de problemas son problemas “fáciles” y rápidos de resolver, como ordenar alfabéticamente un conjunto de palabras. Bajo esas mismas condiciones un problema NP no puede ser resuelto en un tiempo polinómico, sino en un tiempo exponencial, aunque sí se podría resolver rápidamente si se cuenta con una máquina (conceptual) no determinista. (leer más…)
