…o al menos eso asegura el investigador Vinay Deolalikar de los Laboratorios de HP en este trabajo (la imagen de la derecha corresponde a su primera página).
Vinay, que ya había publicado algún artículo relacionado con el tema (en el arXiv podemos ver estos dos), envió un mail a Greg Baker (entre otros) comunicando la publicación de su trabajo y el mismo Greg lo ha publicado en su blog. En esa entrada comenta que el trabajo parece ser serio y además reproduce la opinión del reputado científico de la computación Stephen Cook, que considera el trabajo como un acercamiento relativamente serio a la resolución del problema.
Como comenta Juan Pablo, de confirmarse la validez de la demostración de Deolalikar se va a cometer un fail (no encuentro palabra mejor que la que ha usado el mismo Juan Pablo) tipo el de Andrew Wiles. El ICM se va a celebrar en Hyderabad (India) del 19 al 27 de este mes de agosto, por lo que la revisión de este trabajo no llegará a tiempo. Teniendo en cuenta que Vinay cuenta con 39 años, que la Medalla Fields se entrega en los ICM a matemáticos menores de 40 años y que el próximo no se celebrará hasta dentro de cuatro años…pues eso, blanco y en botella, que de ser válida la demostración Vinay Deolalikar se queda sin Medalla Fields (como Wiles) después de resolver uno de los problemas más importantes (posiblemente el que más) de la Teoría de la Computación. Qué injusto…
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: …o al menos eso asegura el investigador Vinay Deolalikar de los Laboratorios de HP en este trabajo (la imagen de la derecha corresponde a su primera página). Vinay, que ya había publicado algún artículo relacionado con ……
[…] This post was mentioned on Twitter by gaussianos, Alberto Marquez. Alberto Marquez said: si eso es cierto, vale 10^6$ RT @gaussianos: Gaussianos.com: Pues igual resulta que P ≠ NP… http://bit.ly/cSonc6 […]
[…] BlogCyber Security Challenge launch blog « BCS / IITT Institute …Related posts on DeolalikarPues igual resulta que P ≠ NP… | GaussianosIs P vs NP solved? | Current Events | Twitter Trends | Google TrendsMia Farrow | Kevin […]
[…] 12:00h | gaussianos | Leer articulo completo en gaussianos.com […]
esto puede ser un BOMBAZO!!!!! 😀
[…] Pues igual resulta que P ≠ NP gaussianos.com/pues-igual-resulta-que-p-np/ por esparta hace 1 segundos […]
Al menos podría llevarse el millón de dólares del instituto Clay.
He leido algo de este problema, pero honestamente no entiendo de que trata, más allá de que tiene alguna relación con informática. Si alguien pudiese dar una explicación, de seguro que no seré yo el único que lo agradezca 🙂
Esto es una bomba para los informaticos es como resolver la hipotesis de riemmann para los matematicos o comprobar la teoria del todo para los fisicos
http://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP
A veces pienso que no se comprende muy bién a los matemáticos que buscan la resolución de un gran problema. Para ellos el mejor premio es hallar esa solución. Esa es su motivación mas grande. Mucho mejor que cualquier otro premio material que pueda dárseles.
que razón llevas hernan, sin embargo no se si sentirme feliz porque finalmente si ha desvelado este gran «misterio» o si sentirme infeliz por la conclusión tan fatídica para los que nos dedicamos a la computación
Si es horrible saber que es imposible encontrar un algoritmo polinomico para el TSP(problema del agente de viajes) pero esta es la puerta para que los investigadores olviden en encontrar cosas que no existen y centrar todo los esfuerzos en programación lineal,dinamica,algoritmos probabilisticos y heuristicos y redes neuronales.
Como tomara la noticia Charlie Eppes quizas piense en la hipotesis de riemmann
[…] Gaussianos […]
Dado que la demostración es extensa creo que no hay que apresurarse a sacar conclusiones definitivas. Dejemos transcurrir el tiempo necesario para que los expertos verifiquen la prueba.
se sabe aproximadamente lo que tardarán en verificar la demostración¿?
[…] Pues igual resulta que P ≠ NP…, Gaussianos [9 de agosto de 2010] […]
Aporto unos cuantos links (en Inglés) para aquellos interesados en seguir el tema. realmente están siendo un par de días apasionantes para aquellos interesados en el tema. La demostración se basa básicamente en la Teoria de Modelos Finita y en la teoria «Random k-sat» (que tiene que ver con la teoria de la computación teoricos y con la física estadística). Aunque el tema sigue abierto, expertos en ambos temas están levantando serias objeciones a la demostración. un «polymath wiki» sobre el tema: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper Dos blogs sobre en los que se ha centrado la discusión técnica que luego queda reflejada en… Lee más »
¡Pero si es obvio que
si 
! 
Fuera de broma, espero que se haya resuelto por fin este inquietante enigma. Si los matemáticos siguen a este ritmo, pronto no quedarán ni uno de los Siete…
proaonuiq, hay muchas razones para prestarle atención a esto y no a las que todos los meses aparecen: -viene de un profesional serio -ya tiene trabajos en el área publicados en journals reconocidos (el último, de 2009) -lo que se puede leer, sin uno no es un experto en el tema, deja claro que el autor sabe mucho más que uno (es sorprendente la cantidad de pseudo-demostraciones donde uno puede hallar la falla sin saber casi nada del problema) -la info se filtra desde la comunidad científica Todo esto no quita que la demostración no tenga un error, es más,… Lee más »
[…] 13 en Pues igual resulta que P ≠ NP… […]
Juan Pablo, Gracias por tu comentario. Yo estoy a favor de que se haga lo mismo que se está haciendo en esta ocasión, en todos los casos, incluso los más disparatados. Es decir, hacer un listado con las demostraciones (esto ya existe: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm; me parece una gran página) y para cada demostración discutirla en algún blog y asociarle wiki que agrupe las discusiones, cómo en esta ocasión. Cómo dices, en la mayoria de los casos será muy fácil encontrar el error. Incluso papers llenos de errores pueden aportar buenas ideas, se eliminar ruido informativo, es didáctico y tiene interés para… Lee más »
de hecho, no quería que se difundiese (lo dice en su página personal, y ahora agrega una versión posterior, revisada)!
Entonces se explica que el autor no haya aparecido en las discusiones de los blogs. Posiblemente le han desbordado los acontecimientos. Pero ya que la situación está así pienso que debería establecer una comunicación directa con los expertos en el blog de discusión. Todo el proceso de revisión colectivo se aceleraría si de vez en cuando diese alguna explicación directa de algún concepto o paso dudoso. Sobre la capacidad del autor no hay duda (no hay más que ver sus publicaciones y trayectoria), pero algunos expertos se están quejando de la forma poco matématica que tiene el «draft» (lógico si… Lee más »
Página pessoal de Vinay Deolalikar:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/
Link da versão actual (12/08/10) do artigo indicada na página pessoal :
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf
Gracias Americo !
Parece que el tema se está cerrando en falso.
Parece que al final todo ha quedado en intento.
http://francisthemulenews.wordpress.com/2010/08/12/la-opinion-de-terence-tao-sobre-la-demostracion-de-p%E2%89%A0np-de-deolalikar/
Ultimas novedades. Nueva versión muy resumida (3 páginas) de la estrategia de demostración. Afirma que los posibles problemas señalados tienen solución. Todavía no aparecen las demostraciones por ninguna parte , lo cual no va a satisfacer a los más puristas…
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf
Realmente interesante, aunque si se va a decidir negativamente la cuestión (P!=NP) casi preferiría que siguiera abierto el tema… Por otra parte (por algunos comentarios), me parece exagerado comparar este problema con (ej) la teoría del todo de los físicos, que P!=NP (cosa que [por lo visto] todo el mundo piensa) tendría «poca» repercusión (¡lo comparamos con la teoría del todo!) y aun cuando P=NP «sólo» conseguiríamos un bonus (muy importante eso sí) en nuestra capacidad práctica actual de computación (eso sí, debe encontrarse antes ese algoritmo «mágico» que meta en P algún NP-completo [ej 3-SAT]). En cualquier caso y… Lee más »
Tocando otro tema, y pase lo que pase con esta demostración… ¿no os parece que el límite de 40 años sólo sirve para que la medalla Fields pierda la mitad de su prestigio cada vez que incurre en una injusticia tan flagrante como la de Willes?
Claramente Sive, si al final llega a validarse la demostración tras un periodo de revisión que a priori va a ser largo, le va a pasar a Vinay lo mismo que a Wiles. Como comentario personal, yo quitaría ese límite de edad.
Creo que lo que dice el Doctor de HP de que P!=NP es erroneo, si hay un algoritmo que resuelva el TSP en tiempo P, que no lo hayan visto no quiere decir que no exista, creo que el infinito si es computable y eso hace que P=NP, aunque esta afirmación rompa con la lógica.
Aunque os suene a viejo, yo sí he llegado a extrañas conclusiones:
– SAT está en P
– NP distinto de P
http://www.archive.org/search.php?query=%22Juan%20Manuel%20Dato%22
Incluyo explicación de dónde erra Cook, algoritmo que funciona en Python 3.0, swf que muestra gráficamente cómo funciona y teorema que lo demuestra.
Juan Manuel Dato Ruiz, tus dos proposiciones contradicen «estrepitosamente» resultados intensamente revisados durante los últimos 50 años (y todavía). Tu primera proposición implica (de ser demostrada) que NP=P, pero como la segunda lo niega (y tu documento es ilegible 😛 ), entonces Cook y Leonid se equivocaron hace 40 años (y nadie ha detectado el error hasta ahora). Por otra parte, la forma más simple de hacer una verificación preliminar es implementar y ejecutar el algoritmo, usando tu código en python (que viene sin código de ejemplo de ejecución… 😛 ) no hay ningún resultado. Por ejemplo ejecutando: p1 =… Lee más »
josejuan agradezco infinitamente tu respuesta y te respondo por puntos: – Disculpa, no he introducido cómo se debe usar el código: formulaSAT3(prueba())[0] formulaSAT3(prueba2())[0] como era de esperar tienen que funcionar… de hecho: len(formulaSAT3(prueba())) devuelve «3 soluciones». En mi libro mostré cómo resolver el #P, pero no pude llevarlo a cabo de manera polinomial. Es muy largo de contar, simplemente ese estudio está a medias. Por otro lado, no había probado algo tan específico como el caso (1,0,0): se trata de un bug porque el código no está pensado para algo tan pequeño (para una única cláusula no funciona porque es… Lee más »
Juan Manuel, ¿tu has revisado tu código?, ¿has probado ejemplos?, ¿has contrastado tus resultados?, porque, o tienes una constante multiplicativa muuuuuuuuuy grande o tu algoritmo es muy deficiente (y por supuesto no polinómico).
Intenta ejecutar éstos problemas y contrástalos (por ejemplo) con minisat (fácilmente compilable y usable).
Un simplón ejemplo con sólo 20 variables y 91 claúsulas (con solución) al minisat le lleva 5 milisegundos (de los cuales la mayoría será de leer el problema del disco), mientras que en tu código le he dejado más de once minutos y aún está en ello…
josejuan, el código no lo implementé para contrastarlo con algoritmos que ejecutan resultados probabilísticos. El código simplemente es POLINOMIAL por cómo se ejecuta. Eso es inapelable. Por otro lado, 91 claúsulas para 20 variables me lo cepillo yo con el algoritmo exponencial que propuse en mi libro y que, por supuesto, no resolvía rigurosamente el problema de si P es distinto de NP, pues sólo lanzaba conjeturas. Otra cosa, si en estas máquinas no compensa un algoritmo polinomial, puede que con máquinas más complejas (o si me da por aprovechar el paralelismo, cosa que no he hecho), seguro que funcionará… Lee más »
A propósito, acabo de echar un vistazo a esas comprobaciones (supongo de cuya naturaleza fue hecha) al azar que citabas en ese link. No te parece extraño: – ¿Que pidan instancias que resuelvan el código? ¿Es que no saben hacerse su propio código que genera cláusulas al azar que sean satisfacibles? – ¿Por qué necesitan para sólo 91 cláusulas ni más ni menos que 20 variables? Si te fijas en los casos no suele lllegar al 20% en la relación cláusula/variable, por lo que se favorece el encontrar soluciones al azar. – miniSAT usa «métodos» mientras que mi algoritmo es… Lee más »
En fin, un montón de imprecisiones y sinsentidos…
«La complejidad es cuadrática en espacio y tiempo»
¿Se puede ver la demostración? (rigurosa por supuesto, no vale eso de «…no resolvía rigurosamente el problema de si P es distinto de NP, pues sólo lanzaba conjeturas…»).
josejuan, me cito a mí mismo:
– El libro que escribí fue antes de las demostraciones. Pues el libro se basa en los estudios de #P, no tanto de NP y P.
– En la página (archive.org) muestro una demostración rigurosa en inglés que asegura que SAT es P.
http://www.archive.org/details/ConnectionBetweenSat3AndPBetweenMatch-n
– En esa misma página aparece el funcionamiento del algoritmo gráficamente en castellano en formato swf.
– A propósito, el problema Match-3 también tiene una demostración falsa en la «versión oficial».
Insisto, más no sé que hacer.
En «Part 3. Definition of the problem» dices que vas a definir el problema «match-N» (el cual luego «parece» ser algún set cover) pero no defines (o yo no lo he visto) el problema (qué cosa hay que resolver con la matriz q X N que defines).
Está definido (creo que) «muy jodidamente» en 3.1 También puedes ver en la primera trasparencia de la representación gráfica cómo defino el match-N Consiste en una matriz compuesta por q tuplas y cada tupla de tamaño N, donde los elementos de cada tupla forman parte de un alfabeto de q símbolos. La idea consiste en decir que estos datos conservarán un tipo de relación demanera que representen una permutación. Se trata del conocido problema definido como Match-3, pero con N miembros: Concretamente el match-3 dice que disponemos de varias personas, algunos hombres, otros mujeres y otros niños. Y se trata… Lee más »
A propósito, releyendo tus comentarios te diré que me resulta incómodo hablar con este nivel de educación después de haber recibido un trato de decir «imprecisiones o sinsentidos», obviamente si no rectificas o te defines yo no me veré en la obligación de dar mayores explicaciones. Al fin y al cabo, ¿quién me dice a mí que realmente te interesa conocer mis resultados? ¿O que sabes distinguir entre un bug y un error en la lógica del algoritmo?
Bueno, aclarado, tu proposición 3.4. no es correcta, obviamente no se puede aplicar divide y vencerás en este tipo de problemas (que es lo que haces en Prop 3.4). A cada paso en que divides, te aparecen múltiples caminos que deben ser revisados, llegándose nuevamente a alternativas. No sólo no rectifico, sino que reafirmo: las imprecisiones han quedado patentes y los sinsentidos me han quedado ahora claros (antes leí por encima tu documento, como insististes que ahí estaba la demostración, lo releí). En fin, siento que hayamos derivado en este tono, pero ya digo, la forma más sencilla de hacer… Lee más »
Por cierto, el problema que tu llamas Match-3 es realmente 3 dimensional matching y su generalización (lo que tu llamas Match-N) es Set packing, de todos modos, creo que sería más cómodo (en tu documento) que resolvieras Set cover problem.
No sólo no has entendido lo que yo he llamado una instancia de nombre, sino que además no estoy en absoluto de acuerdo. Así que sí estoy de acuerdo en que no vale la pena esta discusión, buscaré apoyos en quienes entiendan estas definiciones. Nunca aparecen múltiples caminos, y la proposición 4.3 no es sino un mecanismo de implementación de las dependencias de reunión para una base de datos en 5FN. Para no tener que usar esos términos, redefiní los conceptos. Por otro lado, estoy de acuerdo conque el que yo llamo matchN debería ser visto como un problema tipo… Lee más »
Siento escribir otro post tan pegado, pero parece que cuando los sentimientos afloran la lógica cierra la mente en banda.
Pongo un ejemplo y ya me marcho: Si José es el marido de María en la Biblia y María es la madre de Jesús en la Biblia. Entonces José es el marido de la madre de Jesús en la Biblia. Y no existen 2^n combinaciones salvo una sola.
Yo soy ateo, pero no me sabía ningún ejemplo no religioso donde hubiera una relación padre-madre-hijo que fuera tan famosa.
Bueno, ¿alguien sabe algo nuevo sobre este tema? ¿Es errónea o correcta, o aún está en revisión?
Te respondería, pero en este blog censuran mensajes.
Fractalon, se sabe que era incorrecta. Se encontró algún error que parece que Deolalikar no pudo solucionar.
JMDato, ¿? ¿Me podrías explicar a que te refieres con «censurar mensajes»?
Pues por lo visto ahora un tal Xinwen Jiang dice que si que P=NP:
http://arxiv.org/abs/1305.5976
Habrá también que esperar a que se confirme/desmienta