¿Cómo citar el nuevo resultado del isomorfismo gráfico de Babai?

16

Recientemente, Babai ha publicado un artículo sobre STOC 2016 alegando que el isomorfismo gráfico puede resolverse en tiempo cuasipolinomial.

A principios de 2017, Babai se retractó del reclamo cuasipolinomial debido a algunos errores graves encontrados por Harald Helfgott. Como lo explicó el propio Babai, esta falla hace que la mejora sea más modesta en términos de tiempo de ejecución.

Aproximadamente 5 días después de retractarse del reclamo cuasi-polinomial, Babai publicó otra actualización en su página de inicio argumentando que había reparado la falla en la prueba, restaurando de esta manera el tiempo de ejecución cuasi-polinomial.

Tengo que decir que después de este cambio rápido en el estado de la corrección de la prueba, normalmente ignoraría por completo el nuevo artículo hasta que se publicara en una revista muy respetada.

Pero como Babai es Babai, la mayoría de la comunidad da por sentado su palabra, al menos públicamente, a pesar de que la nueva versión del documento con todas las correcciones implementadas ni siquiera está disponible. Tenga en cuenta que incluso las grandes personas cometen errores y existe una posibilidad no despreciable de que la nueva solución también tenga un defecto, etc.

Entonces, ¿cómo debo citar el nuevo resultado?

  1. Cite el documento STOC que reclama el cuasipolinomio en el límite superior.
  2. Cite el documento STOC explicando que tiene una falla grave y que el tiempo real de ejecución mejora el límite inferior subexponencial anterior.
  3. Cite el documento STOC diciendo que tenía una falla que fue arreglada por Babai.
  4. No cite en absoluto, y establezca el límite superior anterior de como el límite superior establecido actual.2O(norte)
graph-isomorphism Nadie
fuente
8
Creo que (1) sería una mala opción, dado que la falla fue señalada y reconocida como correcta (es decir, la falla original no fue impugnada, sino que fue reconocida, por el autor), la opción (1) no No refleje la mejor información disponible actualmente. Además de 2-4, también hay otras opciones: por ejemplo, podría simplemente proporcionar información completa (toda la historia como se indicó anteriormente), o podría citar la versión STOC pero decir que una versión revisada por pares con la solución del defecto conocido no aún apareció, y también cita el mejor límite anterior.
Joshua Grochow
77
Puede escribir "Babai ha anunciado un algoritmo ..." y dar un puntero a su sitio web.
Chandra Chekuri
3
Depende de por qué estás citando su papel. Si tiene un resultado que se basa en el suyo, puede hacer que el suyo sea condicional y luego citar su artículo como escribió Chandra. Si lo está citando pero no lo está usando, puede volver a citarlo como escribió Chandra. En ambos casos, enlace a su publicación o su borrador. Cualquier persona interesada puede verificar si es correcta o no por sí misma.
Kaveh
77
Por cierto, no creo que Babai sea tratado de manera diferente a otros expertos en sus campos de especialización, esa parte de su publicación no se limita a la cuestión de cómo citar un reclamo o un borrador del documento que aún está en revisión. Hace que su publicación parezca una queja, por lo que sugeriría eliminarla. La diferencia en el tratamiento en comparación con las personas aleatorias desconocidas que no han publicado ningún resultado importante en el campo y, por lo tanto, aún no han demostrado ninguna experiencia en el campo, se justifica como en cualquier otro lugar.
Kaveh
@Kaveh Estoy totalmente de acuerdo con el punto de vista de Kaveh.
Tayfun Pay

Respuestas:

5

En primer lugar, desalentaría la presentación de un documento incondicional que dependa del resultado cuasi polinomial, si eso es para lo que desea la cita. Reformule el resultado como condicional a la existencia de un algoritmo GI cuasi-polinomial y establezca en una nota al pie que Babai pudo haber probado esto pero que el documento no está disponible públicamente. En este caso, no es necesaria una cita porque no necesita el resultado para el papel.

En cualquier otro contexto, no creo que sea particularmente necesario citar un artículo disponible; citar su sitio web está bien. Depende un poco de lo que esté escribiendo, pero recomendaría afirmar algo como "se cree ampliamente que GI tiene solución en tiempo cuasipolinomial y Laszlo Babai ha anunciado una prueba de esto [cita a la página web donde él hace el reclamo] ".

Una ventaja notable de citar su reclamo en línea es que su sitio web contiene sus propias palabras sobre el reclamo actual y un enlace a su preimpresión.

Stella Biderman
fuente
66
(Yo tampoco voté en contra). No estoy tan seguro de comprar que la primera mitad de su oración (se cree ampliamente que GI está en QP) era cierta antes del anuncio de Babai. Creo que antes del anuncio de Babai, incluso la opinión sobre si GI estaba en QP probablemente estaba más dividida que, por ejemplo, las opiniones sobre P vs NP (solo como un punto de comparación para algo "ampliamente creído"). Después del anuncio de Babai, creo que la opinión aún está dividida sobre si GI terminará en P.
Joshua Grochow