El problema en cuestión se conoce como P vs NP y se ocupa de los límites fundamentales de la computación. Dicho brevemente, P es la clase de los problemas "fáciles", eso que pueden resolverse mediante un algoritmo en un tiempo razonable.NP pertenece a esa clase de problemas que son fáciles de comprobar, si damos una respuesta, podemos comprobarla, aunque sea difícil de resolver.El problema P = NP, todavía sigue sin resolver después de 40 años, pese a una recompensa $ 1.000.000 que responda a la pregunta si estas dos clases son idénticas
|
etiquetas: p , np , el viajante