Como citar o novo resultado de isomorfismo gráfico de Babai?

16

Recentemente, Babai publicou um artigo no STOC 2016, alegando que o isomorfismo do gráfico pode ser resolvido em tempo quase-polinomial.

No início de 2017, Babai retirou a reivindicação quase-polinomial devido a alguns erros graves encontrados por Harald Helfgott. Conforme explicado pelo próprio Babai, essa falha torna a melhoria mais modesta em termos de tempo de execução.

Cerca de 5 dias após a retirada da alegação quase polinomial, Babai postou outra atualização em sua página inicial, argumentando que ele havia corrigido a falha na prova, restaurando assim o tempo de execução quase polinomial.

Devo dizer que, após essa rápida mudança no status da correção da prova, eu normalmente ignoraria completamente o novo artigo até que ele fosse publicado em uma revista bem respeitada.

Mas como Babai é Babai, a maioria da comunidade está dando como certa a palavra dele, pelo menos publicamente, mesmo que a nova versão do documento com todas as correções implementadas ainda não esteja disponível. Observe que mesmo grandes pessoas cometem erros e há uma chance não negligenciável de que a nova correção também tenha uma falha e assim por diante.

Então agora, como devo citar o novo resultado?

  1. Cite o documento STOC reivindicando o limite superior quase-lipinomial.
  2. Cite o documento STOC explicando que há uma falha grave e que o tempo de execução real melhora o limite inferior subexponencial anterior.
  3. Cite o documento do STOC dizendo que havia uma falha que foi corrigida por Babai.
  4. Não cite nada e indique o limite superior antigo de como o limite superior estabelecido atualmente.2O(n)
Nobo Dy
fonte
8
Eu acho que (1) seria uma má opção - já que a falha foi apontada e reconhecida como correta (ou seja, a falha original não foi contestada, mas foi reconhecida pelo autor), a opção (1) não reflete as melhores informações disponíveis no momento. Além do 2-4, também existem outras opções - por exemplo, você pode apenas fornecer informações completas (a história toda, como acima), ou você pode citar a versão do STOC, mas dizer que uma versão completa e revisada por pares com a correção da falha conhecida não foi encontrada. ainda apareceu e cite também o melhor limite anterior.
Joshua Grochow 18/03/19
7
Você pode escrever "Babai anunciou um algoritmo ..." e indicar o site dele.
Chandra Chekuri 19/03/19
3
Depende do motivo pelo qual você está citando o trabalho dele. Se você tem um resultado que se baseia no dele, pode tornar o seu condicional e depois citar o artigo dele como Chandra escreveu. Se você o está citando, mas não o está usando, pode citá-lo novamente como Chandra escreveu. Nos dois casos, um link para o seu post ou / e seu rascunho. Qualquer pessoa interessada pode verificar se está correta ou não.
19417 Kaveh
7
No entanto, não acho que Babai seja tratado de maneira diferente dos outros especialistas em suas áreas de especialização; essa parte do seu post não se refere à questão de como citar uma reivindicação ou rascunho que ainda está sendo analisado. Faz com que sua postagem pareça uma reclamação, então sugiro removê-la. A diferença de tratamento em comparação com pessoas aleatórias desconhecidas que não publicaram nenhum resultado importante no campo e, portanto, ainda precisam provar que qualquer conhecimento nesse campo é justificada como em qualquer outro lugar.
19417 Kaveh
@ Kaveh Eu concordo totalmente com o ponto de vista de Kaveh.
Tayfun Pay

Respostas:

5

Primeiramente, eu desencorajaria a submissão para publicação de um artigo incondicional que depende do resultado quase polinomial, se é para isso que você deseja a citação. Reformule o resultado como condicional à existência de um algoritmo GI quase polinomial e declare em uma nota de rodapé que Babai pode ter provado isso, mas que o documento não está disponível ao público. Nesse caso, nenhuma citação é necessária porque você não precisa do resultado para o artigo.

Em qualquer outro contexto, não acho particularmente necessário citar um artigo disponível - mencionar que o site dele é bom. Depende um pouco do que você está escrevendo, mas eu recomendaria afirmar algo como "acredita-se amplamente que a IG é solucionável em um tempo quase-polinomial e uma prova disso foi anunciada por Laszlo Babai [citação na página em que ele faz a reivindicação]. "

Uma vantagem notável de citar sua reivindicação on-line é que seu site contém tanto suas próprias palavras quanto à reivindicação atual e um link para sua pré-impressão.

Stella Biderman
fonte
6
(Também não diminuí a votação.) Não tenho tanta certeza se comprei que a primeira metade da sua sentença (acredita-se que o IG está no QP) era verdadeira antes do anúncio de Babai. Acho que antes do anúncio de Babai, mesmo a opinião sobre se o IG estava no QP provavelmente estava mais dividida do que, digamos, as opiniões sobre P vs NP (apenas como um ponto de comparação para algo "amplamente aceito"). Depois do anúncio de Babai, acho opinião ainda está dividida sobre se GI vai acabar em P.
Joshua Grochow