Cambalache 3,14 - La vidriera irrespetuosa

Presunta prueba de que P no es igual a NP

Me avisa Santiago Gala por gTalk que ha visto un tuit apuntando a un artículo en arxiv.org con una presunta prueba de que P no es igual a NP.

El autor de la presunta prueba es Sten-Ake Tarnlund, al parecer catedrático de Ciencias de la Computación en la Universidad sueca de Uppsala, aunque es difícil encontrar información sobre él en la red. De hecho, no aparece en el directorio del departamento al que se supone pertenece. Tiene cuatro artículos indexados en la ISI Web of Knowledge, tres de Informática y uno de Psicología. Ha sido editor de actas de congresos y también aparecen algunas comunicaciones en congresos, la mayoría alrededor de 1980. Seguiré buscando a ver si encuentro un currículum completo.

Le he echado un vistazo muy por encima al artículo y no me acaba de convencer, pero sólo una revisión exhaustiva por especialistas en el tema podrá decidir si la prueba es correcta o no. Desde luego, yo no soy la persona adecuada para esa revisión, pues aunque mis temas son lo bastante cercanos para entender la argumentación en líneas generales, necesitaría bastante tiempo de estudio, que no tengo, para entender el artículo completamente.

Si el artículo fuera correcto vale 10⁶ dólares para empezar, pagaderos por el Clay Mathematics Institute dentro de su programa Problemas del Milenio en el que, a semejanza de Hilbert en el congreso de Matemáticos de París de 1990, se proponen 7 problemas cuya resolución tendría suma importancia en Matemática.

Estaremos atentos. Seguiremos informando.

Actualización: Otra (presunta) prueba (del 7 de Abril): P is a proper subset of NP. Pero esta es más normal (y casi seguramente falsa): su autor no tiene ningún artículo en revistas del ISI (WoK).

Actualización: Los especialistas afirman estar cansados de revisar pruebas de P versus NP. Al fin y al cabo, es el síndrome de la cuadratura del círculo, problema con el que pasaba lo mismo: envío masivo de pruebas mal realizadas por inexpertos en el tema. Pero si este señor realmente es catedrático, habrá que tomarlo un poco en serio, de principio. ¿O no? Porque todos conocemos a catedráticos que... ¿pasará lo mismo en Suecia que aquí?

Además ya se sabe: P=NP si y sólamente si P=0 ó N=1.

Actualización: Una búsqueda en arxiv.org sobre NP proporciona (además de artículos sobre la complejidad computacional de algunos problemas) una colección de pruebas, discusiones, refutaciones y contraejemplos de P=NP y P≠NP.

Actualización: Me chica Chewie en los comentarios que el profesor Sten-Ake Tarnlund tiene una pequeña página en la Wikipedia sueca. Al parecer, nació en 1941, lo cual explica que no aparezca en los directorios de la Universidad. Y, siendo mal pensados, me hace creer que esta demostración puede ser un síntoma de ~~chocheo~~ ~~demencia senil~~ trastornos cognitivos. Me extraña que un seminario realizado en Agosto con este resultado no haya tenido más difusión si convenció a los que asistieron.

2008-10-29 23:35 | Categoría: | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/60259

Comentarios

De: Slastrovilonitrotrotrovic

Fecha: 2008-10-29 23:40

Pues sería una putada. Ya me puedo olvidar de viajar en el tiempo, u a otras galaxias...

De: alvaro

Fecha: 2008-10-29 23:56

Algún día explicarás a un profano esto de P y NP, que yo no he sido capaz de entenderlo nunca O:)

De: Zifra

Fecha: 2008-10-30 00:24

sí, pero hoy no, que es tarde

De: Heimy

Fecha: 2008-10-30 00:52

Jorl. Pues nada, como sea cierto, nos tendremos que quedar con aproximaciones a problemas pa' lo que queda :D

De: Zifra

Fecha: 2008-10-30 00:55

Yo creo que es cierto, Lo que no estoy seguro es de que lo hayan probado.

De: Heimy

Fecha: 2008-10-30 12:33

Ya, ya... Que todos asumimos que es cierto (y los criptógrafos los primeros), por supuesto. Pero siempre queda un rayito de esperanza XD

Por cierto, si este señor es/ha sido catedrático, es lógico que no aparezca en directorios. En Wikipedia dice que nació en el 41, así que ya tiene más de 65 tacos.

De: Zifra

Fecha: 2008-10-30 12:55

no lo he encontrado en wikipedia, pasame url

De: Chewie

Fecha: 2008-10-30 13:07

Zifra: http://sv.wikipedia.org/wiki/Sten-Åke_Tärnlund

De: Heimy

Fecha: 2008-10-30 13:44

El artículo en la wiki no tiene sospecha de ser fabricado (pese a ser un stub). La primera edición es de hace dos años y por entonces decían que era catedrático de ciencias de la computación en Uppsala. Es posible que esté desactualizada.

De: Zifra

Fecha: 2008-10-30 13:50

no, creo que la persona existe y nació en 1941 y ha sido un investigador decente en programación lógica, lógica aplicada a la psicología y otros campos

lo que no me creo es que la prueba presentada en agosto haya pasado desapercibida si hubiera tenido visos de ser correcta

al final me acabaré leyendo el artículo. todo sea por procrastinar