Estoy leyendo la página en http://simple.wikipedia.org/wiki/P_versus_NP que establece:
"...la gente quiere saber si hay algún problema NP que no sea P que no sean problemas P. Esto significa que les gustaría saber si hay algún problema en los que la respuesta no pueda ser encontrada fácilmente por un ordenador, pero si alguien Si alguien dice que tiene la respuesta, es fácil usar un ordenador para comprobar si esa respuesta es correcta".
¿No lo demuestran los ejemplos incluidos? El ejemplo 1, por ejemplo, dice:
Sin embargo, si ella propusiera una división de las rocas, sería trivial comprobar si tiene razón. Lo único que habría que hacer es comprobar si la suma de los pesos de cada pila fuera igual, lo que es fácil de hacer para un ordenador, incluso para un número tan grande.
¿No demuestra esto que el método para encontrar una división correcta de las rocas es difícil de calcular pero fácil de verificar?
0 votos
Philip, no entiendo qué es lo que te molesta. A grandes rasgos, y me molesta que Wikipedia dé una definición tan imprecisa, un problema que es NP pero no P no tiene un método sencillo para encontrar una respuesta, pero una vez que se encuentra una respuesta propuesta, es fácil comprobar si esa respuesta es correcta.
4 votos
@Jim Es una página de "wikipedia simple" :)