¿Se ha resuelto el problema del isomorfismo gráfico?

13

La página del problema de isomorfismo gráfico de Wikipedia parece indicar que, no, no se ha resuelto. Sin embargo, un amigo mío señaló un Algoritmo de tiempo polinómico para el isomorfismo gráfico . No soy lo suficientemente sofisticado como para seguir el razonamiento en el documento.

Tengo mi propio intento muy tosco de un algoritmo de tiempo polinómico sin ninguna prueba, pero me gustaría saber si este problema se ha abordado con éxito antes de continuar.

Entonces, ¿se resuelve el problema del isomorfismo gráfico?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
fuente
1
pregunta que vale la pena. En una revisión cibernética, sería mejor si los encuestados / respuestas realmente señalaran errores específicos en el documento en lugar de generalidades. Sin embargo , es cierto que aquí lo que piensan los científicos profesionales de este tipo de esfuerzos. arxiv está lleno de documentos erróneos, muchos sobre P vs NP, pero muchos otros problemas semifamosos atraen esfuerzos de aficionados, por ejemplo, la conjetura de Collatz, primos gemelos, conjetura de Goldbach, etc.
vzn
77
@vzn No creo que tenga sentido perder el tiempo leyendo documentos que seguramente son incorrectos y no arrojan nueva luz sobre el problema.
Yuval Filmus
2
@vzn No entiendo tu queja. La respuesta de DW (publicado una hora antes de su comentario) enlaces a un comentario que hace punto un error específico en el documento arXiv en discusión.
David Richerby
2
@vzn El documento ArXiv contiene un error. No ha sido revisado para corregir ese error. No hay necesidad de más revisión por pares. No tengo idea de lo que estás diciendo es de segunda mano: un contraejemplo es un contraejemplo, independientemente de si te lo comunicó su descubridor o el traficante de drogas que se cuelga detrás de esa barra cutre en la autopista.
David Richerby
1
@vzn Presumiblemente, no fue revisado porque el autor no pudo corregir el error. Tenga en cuenta que ArXiv no permite la retirada de manuscritos, incluso si resultan ser incorrectos.
David Richerby

Respuestas:

23

No. Ese papel parece estar defectuoso. La falla fue explicada en un comentario por Tracy Hall sobre MathOverflow . Un comentario de seguimiento afirma que el autor más tarde se dio cuenta de que hay un defecto en su algoritmo.

Como explica Yuval, no es raro ver intentos de aficionados para resolver estos problemas; Tienden a ser defectuosos. Cuando se trata de resultados sobre problemas abiertos famosos (p. Ej., P vs NP, isomorfismo gráfico, etc.), recomiendo buscar literatura publicada en conferencias y revistas de buena reputación revisadas por pares: la revisión por pares no es perfecta, pero los artículos revisados ​​por pares tienen una probabilidad mucho mayor de ser correctos.

DW
fuente
17

No, el problema del isomorfismo gráfico no se ha resuelto. El documento al que se vincula es de 2007–2008, y no ha sido aceptado por la comunidad científica en general. (Si lo hubiera sido, lo habría sabido).

El isomorfismo gráfico, como muchos otros problemas famosos, atrae muchos intentos de aficionados. Casi siempre están equivocados. Aconsejaría no tratar de abordar este problema sin primero ser competente en matemáticas de nivel de investigación.

Yuval Filmus
fuente
2
Otra forma de tratar este tipo de reclamos por parte de expertos es la imposibilidad o los resultados de barrera. luego, una refutación más informativa se presenta en la forma "el documento usa un tipo de argumento [x] para tratar de resolver el problema del isomorfismo, pero se sabe por [a, b, c] investigaciones que hay una barrera específica para este tipo de enfoque, y el documento parece desconocer esta barrera o revelar específicamente cómo se supera ". Se conocen resultados sobre esto para el problema de isomorfismo y otros problemas clave, por ejemplo, P vs NP.
vzn
1
Intentar problemas no resueltos como este (y fallar ...) puede ser un ejercicio de aprendizaje muy fructífero, si uno tiene la mentalidad correcta.
Nick Alger
sin embargo, algunas objeciones : las pruebas / afirmaciones tienen una validez en cierto grado independiente de la "aceptación por parte de la comunidad científica más amplia" y el conocimiento de ellas por individuos particulares. por ejemplo, cuando se presenta por primera vez una prueba correcta, nadie más que el autor no la acepta de forma inmediata / instantánea. Se puede encontrar más apoyo para esta dinámica en la historia de las matemáticas. y, a veces, pueden transcurrir largos períodos entre la presentación de afirmaciones / afirmaciones y la aceptación, por ejemplo, en el caso de Galois, Ramanujan, etc.
vzn
8

Sería muy dudoso que lo haya hecho (en el sentido de la prueba de la existencia de un algoritmo de tiempo polinómico). Si bien no es imposible que el documento sea correcto, hay varias señales de advertencia:

  1. El autor no ha publicado el resultado en un lugar revisado por pares (incluso después de 7 años).
  2. El autor no parece haber publicado nada más, en ningún lado.
  3. El documento presenta los algoritmos, pero la afirmación de la corrección es un argumento informal sobre la complejidad.
  4. Para un problema que ha resistido los intentos de algunas personas muy inteligentes, las matemáticas en el documento son demasiado simples.
  5. El autor no parece estar afiliado a una institución académica. La nueva versión del documento aclara esto.

Nuevamente, sin que alguien identifique una falla en el papel, estos no son signos infalibles. Quizás el autor tuvo una visión única y luego pasó a una vida completamente diferente, pero el peso de la probabilidad está en contra: las afirmaciones extraordinarias requieren evidencia extraordinaria.

Para dar más detalles sobre (4) dadas las noticias recientes, László Babai reclamó recientemente una mejora importante en el algoritmo de isomorfismo gráfico conocido (todavía no hay una impresión previa, pero aquí se puede encontrar un comentario decente sobre su conferencia pública ), dando un algoritmo de tiempo pseudopolinomial. Babai y sus colegas son definitivamente personas muy inteligentes, y las matemáticas utilizadas para obtener este resultado son difíciles, profundas y abarcan la teoría de grafos y la teoría de grupos. Dado el peso de la probabilidad, este es el nivel esperado para un avance significativo en un problema como este.

Luke Mathieson
fuente
3
Los puntos 1-4 son fuertes, pero 5 es mucho más circunstancial.
David Richerby
(5) no es correcto. La institución (aparentemente) es la Universidad Técnica de Berlín y está parcialmente patrocinada por el estado. (1) respaldado por este enlace / rastreador de papel. El documento se cita en la página de reclamos de Woeginger .
vzn
3
Babai se retractó del reclamo de tiempo de ejecución cuasipolinomial . Aparentemente hubo un error en el análisis.
Raphael
reclamación cuasipolinomial restaurada
milagro173
3

Laszlo Babai ha afirmado haber encontrado una solución cuasipolinomial para el problema del isomorfismo gráfico a partir del 11 de noviembre de 2015.

... y retiró el reclamo ayer (4/1/2017):

Fuente: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

bharv14
fuente
Desde el enlace que proporcionó: Babai aún no ha publicado una preimpresión, y cuando le pregunté, dijo "pronto, pronto". Hasta entonces.
scaaahu
La pregunta no define qué significaría que el problema del isomorfismo gráfico se cuente como resuelto, pero la interpretación más probable es: que alguien ha encontrado un algoritmo de tiempo polinómico para él, o ha dado evidencia de que no existe dicho algoritmo de tiempo polinómico . Según esa interpretación, esta respuesta no responde la pregunta.
DW
44
Babai se retractó del reclamo de tiempo de ejecución cuasipolinomial . Aparentemente hubo un error en el análisis.
Raphael
reclamación cuasipolinomial restaurada
milagro173