![\"Vinay-Deolalikar-207x300\"](\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/08\/Vinay-Deolalikar-207x300.jpg\" "\\"Vinay-Deolalikar-207x300\\"")
<\/p>\nEl problema P versus NP es uno de los siete Problemas del Milenio de la Fundaci\u00f3n Clay. Vinay Deolalikar, investigador de los Laboratorios de Hewlett-Packard en Palo Alto (California, USA) acaba de anunciar en un art\u00edculo que ha resuelto el problema en el sentido que N no es igual a NP. Si eso fuera as\u00ed, se habr\u00eda hecho acreedor al premio de un mill\u00f3n de d\u00f3lares. Sin embargo, la cuesti\u00f3n no est\u00e1 tan clara.<\/p>\n
<\/p>\n
P versus NP<\/strong><\/p>\n Este es un problema de enorme importancia para la computaci\u00f3n cient\u00edfica. Est\u00e1 relacionado con la rapidez que un ordenador puede realizar una tarea, imaginemos por ejemplo, factorizar un n\u00famero. Esta es una tarea f\u00e1cil si se trata de las que recordamos de nuestros a\u00f1os escolares (recordemos lo de descomponer un n\u00famero en sus factores primos), pero muy compleja cuando hablamos de n\u00fameros muy grandes. El tema de la factorizaci\u00f3n es crucial en criptograf\u00eda; el c\u00f3digo RSA est\u00e1 basado en conocer n\u00fameros primos muy grandes, multiplicarlos y obtener un n\u00famero inmenso cuya descomposici\u00f3n va a ser una tarea tit\u00e1nica y as\u00ed garantizamos el secreto de nuestras comunicaciones.<\/p>\n Una manera precisa de establecer el problema P versus NP en t\u00e9rminos matem\u00e1ticos ser\u00eda esta: Determinar si cada lenguaje aceptado por alg\u00fan algoritmo no determin\u00edstico en tiempo polin\u00f3mico es tambi\u00e9n aceptado por alg\u00fan algoritmo determin\u00edstico en tiempo polin\u00f3mico. Hay que recurrir a la definici\u00f3n de modelo formal de un ordenador, como la m\u00e1quina de Turing, etc. Pero tratamos aqu\u00ed de dar una idea sencilla y no t\u00e9cnica del problema.<\/p>\n Recordemos que un algoritmo es un procedimiento para resolver alg\u00fan problema, y que el agoritmo lo podemos colocar en un ordenador. Una cuesti\u00f3n esencial es la eficiencia del algoritmo, o en otras palabras, cu\u00e1nto tiempo de computaci\u00f3n necesita para resolverlo; m\u00e1s concretamente, \u00bfc\u00f3mo depende el n\u00famero de c\u00e1lculos necesarios de los datos iniciales? Ser\u00e1 un problema P si esta dependencia es poln\u00f3mica y no P (no confundir con NP) si no lo es. En palabras llanas, un problema P es f\u00e1cil de resolver; un problema no P, no.\u00a0 Por ejemplo, colocar una lista de n\u00fameros en orden creciente es un problema P; el problema del viajante (el camino m\u00e1s corto a seguir por un viajante para visitar todas las ciudades de una ruta comercial), se cree que es no P.<\/p>\n Un problema se puede ver que es P si se encuentra un algoritmo adecuado, pero para un problema no P, se trata de probar todos los algoritmos posibles y ver que ninguno resuelve el problema en tiempo polin\u00f3mico.<\/p>\n NP no es lo mismo que no P. NP significa que puede ver f\u00e1cilmente si una soluci\u00f3n es correcta a o no, pero encontrar todas las soluciones ser\u00eda muy largo. Por ejemplo, si nos dan una soluci\u00f3n de un rompecabezas, enseguida veremos si es correcta o no, pero resolverlo puede ser muy d\u00edficil.<\/p>\n Para que nos entendamos con lo que es un\u00a0 problema P y un problema NP, veamos este ejemplo que se puede encontrar en la descripci\u00f3n del mismo en la web de la Fundaci\u00f3n Clay.<\/p>\n Imaginemos una residencia de estudiantes que puede alojar a 100 de ellos, y a la que han concurrido 400 estudiantes. Los 100 estudiantes deben ser alojados en habitaciones dobles, y el director tiene una lista de parejas de estudiantes que no podr\u00edan compartir habitaci\u00f3n. El n\u00famero posible de listas de 100 parejas que se podr\u00edan formar con los 400 estudiantes es enorme, as\u00ed que ser\u00eda una tarea imposible calcularlas todas. Pero si damos una lista, es muy f\u00e1cil ver si es aceptable o no, porque bastar\u00eda ver si contiene o no una de las parejas prohibidas.<\/p>\n Por tanto, si P fuera igual a NP, esto significar\u00eda que ser\u00eda f\u00e1cil de comprobar si las posibles soluciones son correctas, pero tambi\u00e9n f\u00e1cil el encontrar las soluciones.<\/p>\n Por cierto, el buscaminas es un ejemplo de lo que se llama un problema NP completo.<\/p>\n \u00bfLa soluci\u00f3n?<\/strong><\/p>\n El 6 de agosto, Vinay Deolalikar, matem\u00e1tico indio que est\u00e1 trabajando en los Laboratorios de Hewlett-Packard en Palo Alto (California, USA) envi\u00f3 su manuscrito (de 66 p\u00e1ginas en tama\u00f1o de 10pt, 102 p\u00e1ginas en tama\u00f1o de 12pt) a varios matem\u00e1ticos relevantes para su lectura. Ahora prepara la versi\u00f3n final para enviar a una revista.<\/p>\n Como se pueden imaginar, el revuelo en la comunidad matem\u00e1tica est\u00e1 siendo enorme, y matem\u00e1ticos de la talla de Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao, Suresh Venkatasubramanian y otros, est\u00e1n revis\u00e1ndolo todo, y, esto es una caracter\u00edstica muy particular en la comunidad matem\u00e1tica internacional, dispuestos a echar una mano a Vinay en cualquier desarrollo o dificultad en que \u00e9l lo necesite. As\u00ed lo ha declarado p\u00fablicamente Terry Tao.<\/p>\n Recomendamos seguir atentos al tema, los pr\u00f3ximos meses ser\u00e1n apasionantes y dictar\u00e1n si la demostraci\u00f3n de Vinay Deolalikar sobrevivir\u00e1 o no.<\/p>\n ________________________<\/p>\n Manuel de Le\u00f3n<\/strong> (CSIC y Real Academia de Ciencias) es Director del I<\/a>nstituto de Ciencias Matem\u00e1ticas (ICMAT).<\/a><\/p>\n","protected":false},"excerpt":{"rendered":" El problema P versus NP es uno de los siete Problemas del Milenio de la Fundaci\u00f3n Clay. Vinay Deolalikar, investigador de los Laboratorios de Hewlett-Packard en Palo Alto (California, USA) acaba de anunciar en un art\u00edculo que ha resuelto el problema en el sentido que N no es igual a NP. Si eso fuera as\u00ed, se habr\u00eda hecho acreedor al premio de un mill\u00f3n de d\u00f3lares. Sin embargo, la cuesti\u00f3n no est\u00e1 tan clara. P versus NP Este es un problema de enorme importancia para la computaci\u00f3n cient\u00edfica. Est\u00e1 relacionado con la rapidez que un ordenador puede realizar una tarea,\u2026<\/p>\n","protected":false},"author":49,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[1],"tags":[],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":4}},"aioseo_notices":[],"yoast_head":"\n![\"Turing\"](\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/08\/Turing.jpg\" "\\"Turing\\"")
<\/p>\n![\"250px-Complexity_classes_es.svg\"](\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/08\/250px-Complexity_classes_es.svg.png\" "\\"250px-Complexity_classes_es.svg\\"")
<\/p>\n![\"msweep-fig5\"](\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/08\/msweep-fig5.jpg\" "\\"msweep-fig5\\"")
<\/p>\n![\"all\"](\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/08\/all.png\" "\\"all\\"")
<\/p>\n