O problema de isomorfismo gráfico foi resolvido?

13

A página do problema de isomorfismo gráfico da Wikipedia parece indicar que não, não foi resolvida. No entanto, um amigo meu apontou Um algoritmo de tempo polinomial para isomorfismo de gráfico . Não sou sofisticado o suficiente para seguir o raciocínio do artigo.

Eu tenho minha própria tentativa bastante grosseira de um algoritmo de tempo polinomial sem nada como prova, mas gostaria de saber se esse problema foi ou não resolvido com êxito antes de prosseguir.

Então, o problema de isomorfismo gráfico está resolvido?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
fonte
1
pergunta que vale a pena. Em uma revisão cibernética por pares, seria melhor que os respondentes / respostas realmente apontassem erros específicos no artigo, em vez de generalidades. é certo que, porém, aqui está o que os cientistas profissionais pensam sobre esses tipos de esforços. arXiv está cheia de papéis errados, muitos em P vs NP, mas muitos outros problemas semifamous atraem esforços amadores, por exemplo, também a conjectura de Collatz, primos gémeos, Goldbach conjectura, etc.
vzn
7
@ vzn Acho que não faz sentido desperdiçar nosso tempo lendo jornais que são quase certamente incorretos e não lançam nenhuma nova luz sobre o problema.
Yuval Filmus
2
@vzn Não entendo sua reclamação. A resposta de DW (postou uma hora antes de seu comentário) links para um comentário que faz apontar um erro específico no papel ArXiv em discussão.
David Richerby
2
@vzn O artigo do ArXiv contém um erro. Não foi revisado para corrigir esse erro. Não há necessidade de mais revisão por pares. Não faço ideia do que você está dizendo em segunda mão: um contra-exemplo é um contra-exemplo, independentemente de ter sido comunicado a você pelo descobridor ou pelo traficante de drogas que fica por trás daquele bar decadente na rua. a estrada.
David Richerby
1
@vzn Presumivelmente, não foi revisado porque o autor não conseguiu corrigir o erro. Observe que o ArXiv não permite a retirada de manuscritos, mesmo que eles estejam incorretos.
David Richerby

Respostas:

23

Não. Esse papel parece estar com defeito. A falha foi explicada em um comentário de Tracy Hall no MathOverflow . Um comentário posterior afirma que o autor mais tarde percebeu que há uma falha em seu algoritmo.

Como explica Yuval, não é incomum ver tentativas de amadores para resolver esses problemas; eles tendem a ser falhos. Quando se trata de resultados de problemas abertos famosos (por exemplo, P vs NP, isomorfismo de gráficos, etc.), recomendo procurar literatura publicada em conferências e periódicos respeitáveis ​​revisados ​​por pares - a revisão por pares não é perfeita, mas os artigos revisados ​​por pares tem uma probabilidade muito maior de estar correta.

DW
fonte
17

Não, o problema do isomorfismo gráfico não foi resolvido. O artigo ao qual você vincula é de 2007 a 2008 e não foi aceito pela comunidade científica em geral. (Se tivesse sido, eu teria sabido disso.)

O isomorfismo gráfico, como muitos outros problemas famosos, atrai muitas tentativas de amadores. Eles estão quase sempre errados. Eu desaconselharia a tentar resolver esse problema sem primeiro se tornar competente em matemática no nível de pesquisa.

Yuval Filmus
fonte
2
Outra maneira de lidar com esses tipos de reivindicações por especialistas é a impossibilidade ou a barreira dos resultados. então, uma refutação mais informativa segue a forma "o artigo usa um tipo de argumento [x] para tentar resolver o problema do isomorfismo, mas é sabido pelas pesquisas [a, b, c] que existe uma barreira específica para esse tipo abordagem, e o artigo parece desconhecer essa barreira ou revelar especificamente como ela é superada ". existem resultados conhecidos sobre isso para o problema de isomorfismo e outros problemas importantes, por exemplo, P vs NP.
vzn
1
Tentar problemas não resolvidos como esse (e falhar ...) pode ser um exercício de aprendizado muito proveitoso, se alguém entrar com a mentalidade certa.
Nick Alger
no entanto, algumas queixas: as provas / reivindicações têm validade em algum grau, independentemente da "aceitação pela comunidade científica mais ampla" e do conhecimento delas por indivíduos específicos. por exemplo, quando uma prova correta é introduzida pela primeira vez, ela não é imediata / instantaneamente "aceita" por ninguém que não seja o autor. mais suporte para essa dinâmica pode ser encontrado na história da matemática. e, às vezes, longos períodos podem variar entre a introdução de reivindicações / asserções e aceitação, por exemplo, no caso de Galois, Ramanujan etc.
vzn
8

Eu ficaria muito duvidoso disso (no sentido da prova da existência de um algoritmo de tempo polinomial). Embora não seja impossível que o papel esteja correto, existem vários sinais de aviso:

  1. O autor não publicou o resultado em um local revisado por pares (mesmo após sete anos).
  2. O autor não parece ter publicado mais nada, em nenhum lugar.
  3. O artigo apresenta os algoritmos, mas a alegação de correção é um argumento informal sobre a complexidade.
  4. Para um problema que resistiu às tentativas de algumas pessoas muito inteligentes, a matemática no jornal é muito simples.
  5. O autor não parece ser afiliado a uma instituição acadêmica. A nova versão do artigo esclarece isso.

Novamente, sem alguém identificar uma falha no jornal, esses não são sinais de prova de idiotas. Talvez o autor tenha tido um lampejo único de insight e depois tenha mudado para uma vida completamente diferente, mas o peso da probabilidade é contra - afirmações extraordinárias exigem evidências extraordinárias.

Para elaborar (4) notícias recentes, László Babai afirmou recentemente uma grande melhoria no algoritmo de isomorfismo conhecido de grafos (ainda não há pré-impressão, mas um comentário decente sobre sua palestra pública pode ser encontrado aqui ), fornecendo um algoritmo de tempo pseudo-polinomial. Babai e seus colegas são definitivamente pessoas muito inteligentes, e a matemática usada para obter esse resultado é difícil, profunda e abrange a teoria dos grafos e a teoria dos grupos. Dado o peso da probabilidade, esse é o nível esperado para um avanço significativo em um problema como esse.

Luke Mathieson
fonte
3
Os pontos 1 a 4 são fortes, mas 5 é muito mais circunstancial.
David Richerby
(5) não está correto. a instituição (aparentemente) é a Universidade Técnica de Berlim e é patrocinada em parte pelo estado. (1) apoiado por este link / rastreador de papel. o artigo é citado na página de reivindicações da Woeginger .
vzn
3
Babai retirou a alegação de tempo de execução quase-polinomial . Aparentemente, houve um erro na análise.
Raphael
reivindicação quasipolynomial restaurado
miracle173
3

Laszlo Babai alegou ter encontrado uma solução quase-polinomial para o problema de isomorfismo gráfico em 11 de novembro de 2015.

... e retirou a reivindicação ontem (01/04/2017):

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

bharv14
fonte
Pelo link que você forneceu: Babai ainda não divulgou uma pré-impressão e, quando perguntei, ele disse "em breve, em breve". Até então.
Scaaahu
A questão não define o que significaria que o problema do isomorfismo do gráfico fosse contado como resolvido, mas a interpretação mais provável é: que alguém encontrou um algoritmo de tempo polinomial para ele ou forneceu evidências de que esse algoritmo de tempo polinomial não existe. . Sob essa interpretação, esta resposta não responde à pergunta.
DW
4
Babai retirou a alegação de tempo de execução quase-polinomial . Aparentemente, houve um erro na análise.
Raphael
alegação de quase-polinômio restaurada
miracle173