Existe um tipo de resultado de amplificação de gap para o problema de isomorfismo gráfico?

53

Suponha que e G 2 sejam dois gráficos não direcionados no conjunto de vértices { 1 , … , n } . Os gráficos são isomórficos se e somente se houver uma permutação Π tal que G 1 = Π ( G 2 ) , ou mais formalmente, se houver uma permutação Π tal que ( i , j ) seja uma aresta em G 1 se e somente se ( Π ( i ) , Π ( jG1G2{1,…,n}ΠG1=Π(G2)Π(i,j)G1 é uma aresta em G 2 . O problema do isomorfismo de gráfico é o problema de decidir se dois gráficos são isomórficos.(Π(i),Π(j))G2

Existe uma operação em gráficos que produz "amplificação de gap" no estilo da prova de Dinur do teorema do PCP ? Em outras palavras, existe uma transformação computável no tempo polinomial de para ( G ′ 1 , G ′ 2 ) tal que(G1,G2)(G1′,G2′)

  • se e G 2 são isomórficos, então G ′ 1 e G ′ 2 também são isomórficos, eG1G2G1′G2′
  • se e G 2 não são isomórficos, então para cada permutação Π , o gráfico G ′ 1 é " far -far" de Π ( G ′ 2 ) para alguma pequena constante ϵ , onde ϵ -far significa que, se escolhermos ( i , j ) uniformemente ao acaso, em seguida, com probabilidade £ tanto G1G2ΠG1′ϵΠ(G2′)ϵϵ(i,j)ϵ
    • é uma aresta de G ′ 1 e ( Π ( i ) , Π ( j ) ) não é uma aresta de G ′ 2 , ou(i,j)G1′(Π(i),Π(j))G2′
    • não é uma aresta de G ′ 1 e ( Π ( i ) , Π ( j ) ) é uma aresta de G ′ 2 .(i,j)G1′(Π(i),Π(j))G2′
cc.complexity-theory graph-isomorphism pcp Andre Chailloux
fonte
5
@domotorp: “Transformação em tempo polinomial” é uma terminologia padrão para se referir a uma máquina de Turing determinística em tempo polinomial cuja entrada e saída são ambas cadeias. Nesse caso, esta máquina de Turing recebe o par (G1, G2) como entrada e produz o par (G′1, G′2) como saída. Cada gráfico é codificado como uma matriz adjacente, por exemplo.
Tsuyoshi Ito
11
Eu pensei que o teorema do PCP era válido para qualquer problema de NP, então, em particular, ele deve valer para o isomorfismo do gráfico?
Denis
2
@dkuper O autor quer perguntar se existe uma redução de amplificação de gap que reduz instâncias de isomorfismo de gráfico a instâncias de isomorfismo de gráfico com uma lacuna maior; ele não está perguntando sobre o PCP Teorema diretamente, apenas sobre uma técnica usada em provar dureza de aproximação ...
argentpepper
3
Provavelmente um tiro no escuro, mas você poderia mostrar que, se esse fosse o caso, poderia resolver o isomorfismo de grafos em tempo polinomial quântico?
Neal Young
3
É consistente com o estado atual do conhecimento que até o SAT possui algoritmo de tempo linear, portanto, o que você escreveu parece improvável que seja conhecido. Se for o caso, adicione uma referência à sua resposta.
Kaveh

Respostas:

2

Não sei se uma coisa dessas poderia existir ou não. Mas é interessante (e talvez oportuno) notar que tal "amplificação de gap" provavelmente implicaria um algoritmo de tempo quase-polinomial para isomorfismo de gráfico (diferente do anunciado recentemente)

No presente trabalho , um algoritmo de aproximação é dada para o problema "MAX-IGP" de maximizar pares combinados de bordas / não bordas; se reduzirmos de GI para "Gap-MAX-PGI", podemos aproximar-nos para distinguir em que lado da lacuna estamos.

Portanto, acho improvável que a prova de Dinur do teorema do PCP seja diretamente generalizável para um "amplificador de gap", dados os obstáculos que teriam que ser superados.

Joe Bebel
fonte