¿Es la prueba de 2010 de Deolalikar que

8

Hubo recientemente un reivindicado prueba de que PAGS≠nortePAGS . No mucho después de su publicación, surgieron algunos problemas con esta prueba.

Entonces ... ¿la prueba es correcta o no? (Responda esto solo si tiene evidencia ... esta pregunta puede tomar un tiempo hasta que se responda)

np-hardness cc.complexity-theory ripper234
fuente
¿Por qué el voto para cerrar?
Suresh Venkat
77
Creo que la pregunta debería especificar a qué prueba se refiere (al menos mencionar el nombre del autor). Ahora está claro, pero puede que no lo esté en un año a partir de ahora.
Moritz
2
En mi opinión, debe abordar ciertos defectos potenciales en la prueba. Votado para cerrar debido a la falta de especificidad de la pregunta (la calidad de las publicaciones).
2
El enlace se refiere a la historia reciente, aunque prefiero el enlace OP a la wiki de Polymath o la página de Deolalikar que una publicación de slashdot que parece menos permanente
Suresh Venkat

Respuestas:

20

En una palabra: no.

Parece que hay algunas fallas fatales en la prueba propuesta por Deolalikar. La verdadera pregunta ahora es si la "prueba" tiene alguna idea útil sobre la cual se pueda construir. En cualquier caso, parece que la prueba en su forma actual simplemente no es correcta y tampoco se puede corregir. Por otro lado, Deolalikar no ha renunciado a la prueba, así que supongo que no es el final.

Puede encontrar una actualización aquí: http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/

Tomer Vromen
fuente