Dos gráficos G, H son isomórficos si hay un re-etiquetado de los vértices de G que produce H, y viceversa. El problema del isomorfismo gráfico (GI) es decidir si dos dados son isomorfos. Además de su interés práctico, fue identificado por Karp en 1972 como de complejidad desconocida, es uno de los pocos candidatos naturales restantes para un problema intermedio NP y condujo a la creación de la clase de complejidad AM.
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...
El problema del isomorfismo gráfico (IG) es posiblemente el candidato más conocido para un problema NP-intermedio . El algoritmo más conocido es el algoritmo sub-exponencial con tiempo de ejecución . Se sabe que GI no esNP-completo a menos que lajerarquía polinómica secolapse.2O ( n...
Dado un nuevo problema en NPNP\mathsf{NP} cuya verdadera complejidad está en algún lugar entre y NP-complete, hay dos métodos que sé que podrían usarse para demostrar que resolver esto es difícil:PP\mathsf{P} Demuestre que el problema es GI completo (GI = isomorfismo gráfico) Muestre que el...
No determinismo Bounded asocia una función con una clase de las lenguas aceptadas por las máquinas de Turing deterministas-delimitada de recursos, para formar una nueva clase - . Esta clase consta de aquellos lenguajes que son aceptados por alguna máquina de Turing no determinista obedece a los...
Es fácil ver que el isomorfismo gráfico (IG) está en NP. Es un gran problema abierto si GI está en coNP. ¿Hay posibles candidatos de propiedades de gráficos que se puedan usar como certificados coNP de IG? ¿Alguna conjetura que implique ? ¿Cuáles son algunas implicaciones de G I ∈ c o N P...
Supongo que leí demasiados documentos ambiciosos de CoRR . El problema es que esos documentos no son revisados por pares, pero a menudo suenan interesantes y pasan verificaciones básicas de plausibilidad. O tal vez no, y solo necesito mejorar mis verificaciones de plausibilidad. Aquí hay una...
Estoy tratando de entender la relación entre el isomorfismo gráfico y el problema oculto de subgrupos. ¿Hay una buena referencia para
Ha pasado más de un año desde su retracción y corrección de enero de 2017. ¿Hay novedades? Si no, ¿es normal que la validación demore tanto? Esperaría que recibiera mucha atención. ¿Alguien notable ha hablado para apoyar / dudar del resultado cuasi
Motivado por el comentario de Fortnow en mi publicación, Evidencia de que el problema del isomorfismo gráfico no es NPNPNP -completo , y por el hecho de que GIGIGI es un candidato principal para NPNPNP -problema intermedio (no NPNPNP -completo ni en PPP ), estoy interesado en evidencias conocidos...
Inspirado por la pregunta de factoraje conocido como P-hard , me pregunto cuál es el estado actual de conocimiento similar sobre la dureza del isomorfismo gráfico. Estoy seguro de que actualmente no se sabe si GI está en P, pero: ¿Cuál es la clase más grande actualmente conocida que GI es más...
Mientras pensaba en la complejidad de probar el isomorfismo de los gráficos asimétricos (vea mi pregunta relacionada sobre teoría), me vino a la mente una pregunta complementaria. Supongamos que tenemos una máquina de Turing de tiempo polinomial que en la entrada genera un gráfico con nodos.M 1 n...
Actualmente estoy haciendo una encuesta bibliográfica sobre el problema del isomorfismo gráfico (GI). Me gustaría saber algunas preguntas abiertas relacionadas con lo siguiente ¿Cuáles son los parámetros del gráfico para los que la trazabilidad de parámetros fijos de GI es un problema abierto?...
Estoy leyendo sobre las clases de gráficos para los que isomorfismo de grafos ( ) se encuentra en . Uno de esos casos son los gráficos de valencia acotada (máximo sobre el grado de cada vértice) como se explica aquí . Pero lo encontré demasiado abstracto. Estaría agradecido si alguien me puede...
Estoy haciendo una revisión de la literatura sobre el problema del isomorfismo gráfico. La mayoría de los trabajos que estoy leyendo están escritos por EM Luks y Laszlo Babai. Estos documentos utilizan el conocimiento de alto nivel de la teoría de grupos y la teoría de la complejidad. Como soy...
Dado el grupo de simetría y dos subgrupos y , ¿se mantiene ? G , H ≤ S n π ∈ S n G π ∩ H = ∅SnorteSnorteS_nG , H≤ Snortesol,H≤SnorteG, H\leq S_nπ∈ Snorteπ∈Snorte\pi\in S_nG π∩ H= ∅solπ∩H=∅G\pi\cap H=\emptyset Hasta donde yo sé, el problema se conoce como el problema de intersección de coset. Me...
El problema de automorfismo libre de puntos con punto fijo solicita un automorfismo gráfico que mueva al menos k ( n ) nodos. El problema es N P -completo si k ( n ) = n c para cualquier c > 0.kkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Sin embargo, si entonces el problema es el tiempo...
Estoy interesado en este problema: dado un gráfico no dirigido , ¿hay una partición de G en los gráficos G 1 ( E 1 , V 1 ) y G 2 ( E 2 , V 2 ) de modo que G 1 y G 2 son isomorfos?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Aquí se divide en...
¿Es el caso de los gráficos muy regulares el más difícil para las pruebas de GI? donde "más duro" se usa en algún sentido de "sentido común", o "en promedio", por así decirlo. Wolfram MathWorld menciona algunos "gráficos patológicamente difíciles". ¿Qué son? Mi conjunto de muestras de 25...
En el artículo An Efficient Algorithm for Graph Isomorphism de Corneil y Gotlieb, 1970, se estableció una conjetura en la que se basó el algoritmo para resolver GI en el tiempo polinomial. A saber: que los gráficos representativos exhiben la división de automorfismo del gráfico...
No se sabe si isomorfismo gráfico (GI) para gráficos fuertemente regulares (SRGS) está en P . ¿Hay alguna pista de que podría o no ser GI -Complete? ¿Hay alguna consecuencia fuerte en tales casos? (Similar a la creencia de que GI puede no ser