Consequências de um algoritmo de tempo quase-polinomial para o problema de isomorfismo de grafos

40

O problema do isomorfismo de grafos (IG) é sem dúvida o candidato mais conhecido para um problema intermediário de NP . O algoritmo mais conhecido é o algoritmo subexponencial com tempo de execução . Sabe-se que o IG não éNP-completo a menos que ahierarquia polinomialcolapsa.2O(nlogn)NP

Quais seriam as consequências teóricas da complexidade de um algoritmo de tempo quase-polinomial para o problema de Isomorfismo de Gráfico?
Um algoritmo de tempo quase polinomial para GI refutaria quaisquer conjecturas famosas na teoria da complexidade?


Outros problemas semelhantes, como o problema Conjunto mínimo de domínio nos torneios, o problema de isomorfismo de grupo e o problema de isomorfismo de torneio, têm algoritmos de tempo quase polinomial ( QP ). Os dois problemas posteriores são reduzidos em tempo polinomial para GI.

Podemos reduzir eficientemente o problema do Conjunto Dominante Mínimo em Torneios para GI?
Existe alguma conjectura que exclua a IG ser difícil para o QP?

Atualização (14-12-2015) : Babai publicou um rascunho preliminar no arXiv para seu algoritmo de tempo quase-polinomial para GI.

Atualização (04-01-2017) : Babai retirou a alegação de que o algoritmo está no tempo quase-polinomial, de acordo com a nova análise, que o algoritmo está no tempo subexponencial que está dentro de2 n o ( 1 ) .expexp(O~(lgn))2no(1)

Atualização (09-01-2017) : Babai restabeleceu a reivindicação de tempo quase-polinomial, substituindo o procedimento incorreto por outro mais eficiente.

Mohammad Al-Turkistany
fonte
6
Eu acho que muitas pessoas pensam que ele tem um algoritmo de tempo polinomial, e esse algoritmo AFAIK não teria consequências teóricas de complexidade.
Huck Bennett
7
AC0
14
Depois de dois anos, acredito que temos uma resposta. Laszlo Babai provou que a IG possui um algoritmo de tempo quase polinomial. Fonte: lucatrevisan.wordpress.com/2015/11/03/...
user3415207
8
@ user3415207 Babai retirou a reivindicação de tempo de execução quase-polinomial . Aparentemente, houve um erro na análise.
Raphael
6
@ Rafael ... e Babai restaurou sua reivindicação (mesmo link que o seu).
Danny

Respostas:

5

Até onde sei, se você perguntar simplesmente sobre as consequências do simples fato (como uma caixa preta) de que o IG está no QP, acho que a resposta é muito pequena. A única coisa em que consigo pensar, que não é um teorema, mas uma consequência para as direções da pesquisa, é agrupar o isomorfismo. Como o GroupIso se reduz a GI e nem sabemos se o GroupIso está em P, colocar o GroupIso em P pode ser visto como um obstáculo importante para colocar o GI em P (se você acha que esse pode ser o caso).

nlogn+O(1)2O~(n)

Joshua Grochow
fonte
nO(loglogn)
nO(loglogn)cc
@ JoshuaGrochow Você concorda comigo que a abordagem adotada por François Le Gall e David J. Rosenbaum em Problemas no grupo e no isomorfismo das cores faz sentido? Ou pelo menos eles tratam algumas questões que poderiam surgir depois de obter um entendimento básico do resultado de László Babai?
Thomas Klimpel
@ ThomasKlimpel: Concordo que o trabalho deles faz sentido, embora ainda não veja como tirar proveito de suas idéias (apesar de entender a maioria das provas de Babai).
Joshua Grochow
βkP
2

Σ

Emil Jeřábek apoia Monica
fonte
0

Quais seriam as consequências teóricas da complexidade de um algoritmo de tempo quase-polinomial para o problema de Isomorfismo de Gráfico?

Mais ou menos semelhantes às conseqüências do algoritmo de tempo polinomial determinístico para testes de primalidade, o algoritmo de tempo polinomial determinístico para programação linear e o outro caso em que algoritmos praticamente eficientes (randomizados) (com exemplos patológicos raros em que o algoritmo se tornou ineficiente) eram conhecidos. e em uso por um longo tempo. Confirma a conjectura de que a eficiência prática é um bom indicador para a existência de algoritmos teóricos determinísticos que superam as questões dos raros exemplos patológicos.

Um algoritmo de tempo quase polinomial para GI refutaria quaisquer conjecturas famosas na teoria da complexidade?

Não, as conjecturas preferem ir para o local oposto, a saber, o IG está em P. Como o IG está em NP, não será possível refutar esse tipo de conjectura tão cedo.

Podemos reduzir eficientemente o problema do Conjunto Dominante Mínimo nos Torneios para GI?

O Conjunto de Dominação Mínimo não é um problema de isomorfismo, portanto, não há razão para que se deva reduzir o IG.

Existe alguma conjectura que exclua a IG ser difícil para o QP?

Nem sabemos como reduzir o problema de isomorfismo de cordas para GI, e isso é pelo menos um problema de isomorfismo. A prova de Babai mostrou que o isomorfismo das cordas estava no QP, então ... E o que está sendo difícil para o QP mesmo? Difícil sob reduções de tempo polinomiais?


Da introdução de No grupo e problemas de isomorfismo de cores por François Le Gall e David J. Rosenbaum

A complexidade dos problemas dos testes de isomorfismo é digna de estudo, porque são questões computacionais fundamentais e também porque muitos deles não são conhecidos por estarem em P, mas, no entanto, parecem ser mais fáceis do que os problemas completos do NP. O mais estudado é o problema do isomorfismo gráfico.

GIGrIsão definidos (no artigo acima, mas os autores se perguntam, com razão, por que ninguém fez isso antes), que adicionam as peças que faltam no problema do isomorfismo das cordas. (E o problema do isomorfismo das cores é apenas um nome diferente para o problema do isomorfismo das cordas. O problema do automorfismo das cores dos nomes remonta aos documentos iniciais de Babai e Luks; o isomorfismo das cadeias de nomes ocorre mais tarde em seu artigo sobre rotulagem canônica.)

GI


Edit: Esta resposta foi dada no contexto da retração do resultado de Babai, antes que ele anunciasse uma correção. Isso sugere que a leve generalização do problema de isomorfismo gráfico sugerida pelo problema de isomorfismo de cordas é o problema realmente importante. A expectativa implícita aqui é que qualquer algoritmo razoável para o problema de isomorfismo de gráfico levará a um algoritmo semelhante para o problema de isomorfismo de gráfico generalizado. O problema generalizado é o tempo polinomial equivalente ao problema do estabilizador de set , o problema de interseção de grupo , o problema de interseção de coset, o problema de transportador de set , ... A idéia por trás dessa expectativa é que o problema generalizado ocorra na parte recursivade qualquer algoritmo razoável, portanto, ele deve ser tratado de qualquer maneira. (E é bem possível que o problema generalizado seja o tempo polinomial equivalente ao isomorfismo do gráfico.)

Agora, os comentários de Joshua Grochow indicam que não tive êxito em explicar a importância conceitual das peças que faltam no problema do isomorfismo das cordas. Para estruturas infinitas, pode ser mais fácil perceber que um isomorfismo válido não deve apenas preservar a estrutura fornecida, mas também pertencer a uma categoria apropriada de funções (por exemplo, a categoria de funções contínuas). Para estruturas finitas, o fenômeno análogo ocorre principalmente para estruturas quocientes, onde a categoria apropriada de funções deve ser compatível com os quocientes especificados. O material de Johnson é um exemplo típico desses quocientes, por exemplo, a lógica da partição está trabalhando nos dois subconjuntos de elementos de um conjunto de bases. Observe também que restringir a categoria permitida para os isomorfismos geralmente facilita o problema do teste de isomorfismo,

O problema com generalizações do problema de isomorfismo do gráfico é onde parar. Por que não generalizar a ponto de abranger o problema de isomorfismo do grupo de permutação? Essa pergunta é realmente difícil, pois muitos resultados não triviais para o isomorfismo de gráfico provavelmente também serão transferidos para o isomorfismo do grupo de permutação. Mas aqui parece mais razoável tratar a teoria dos grupos de permutação computacional como um assunto por si só, mesmo que tenha de fato uma conexão estreita com o problema do isomorfismo gráfico.

Thomas Klimpel
fonte
11
Sn
11
@ JoshuaGrochow Para iso de cores, as cores são apenas números arbitrários (wlog restrito a [n]). Para iso de string, as strings são fornecidas sobre um alfabeto finito fixo. Eu pensei que era um alfabeto binário, mas me lembrei disso. Acabei de lembrar que fiquei inicialmente confuso se iso de cor era apenas um nome diferente para iso de string. Então, quando eu decidi ler o jornal depois que Laszlo retirou sua alegação, pareceu uma diferença para mim. Talvez seja realmente uma diferença, porque "sobre um alfabeto finito" se comunica "conserte seu alfabeto finito favorito, não fará nenhuma diferença". Que é verdade.
Thomas Klimpel
11
logn[n]
11
@ JoshuaGrochow Isso é exatamente o que eu quis dizer com isso não fará nenhuma diferença ". O que é verdade. Agora, tentei abordar seu comentário" Isomorfismo de string / isomorfismo de cor não se enquadra nessa classe ". Gostei de aprender algumas lições de Andreas Blass e Yuri Gurevich, que também tentam se concentrar em pontos conceituais.Estou feliz que Babai tenha corrigido seu algoritmo agora, de modo que não sinto nenhuma obrigação (ou pressão) de investigar se isomorfismo gráfico e isomorfismo de cordas são equivalentes no tempo polinomial . (que foi o contexto por isso que escrevi essa resposta.)
Thomas Klimpel
Estou confuso por que você compara o progresso no IG com os resultados da des randomização.
precisa saber é o seguinte