Suponga que y son dos gráficos no dirigidos en el conjunto de vértices . Los gráficos son isomórficos si y solo si hay una permutación tal que , o más formalmente, si hay una permutación tal que es una ventaja en si y solo if es una ventaja en . El problema del isomorfismo gráfico es el problema de decidir si dos gráficos dados son isomorfos.
¿Existe una operación en gráficos que produzca "amplificación de huecos" al estilo de la prueba de Dinur del teorema de PCP ? En otras palabras, ¿hay una transformación computable de tiempo polinómico de a tal manera que
- si y son isomorfos, entonces y también son isomorfos, y
- si y no son isomórficos, entonces para cada permutación , el gráfico es " -far" de para alguna pequeña constante , donde -far significa que si elegimos de manera uniforme al azar, a continuación, con una probabilidad cualquiera
- es un borde de y no es un borde de , o
- no es un borde de y es un borde de .
cc.complexity-theory
graph-isomorphism
pcp
Andre Chailloux
fuente
fuente
Respuestas:
No sé si tal cosa podría existir o no. Pero es interesante (y tal vez oportuno) notar que tal "amplificación de brecha" probablemente implicaría un algoritmo de tiempo cuasipolinomial para isomorfismo gráfico (diferente al recientemente anunciado)
En este documento , se proporciona un algoritmo de aproximación para el problema "MAX-PGI" de maximizar pares coincidentes de bordes / no bordes; si reducimos de GI a "Gap-MAX-PGI", entonces podemos aproximarnos para distinguir de qué lado de la brecha nos encontramos.
Por lo tanto, creo que es poco probable que la prueba de Dinur del teorema de PCP sea directamente generalizable a tal "amplificador de brecha", dados los obstáculos que tendrían que ser superados.
fuente