¿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...
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...
Considere el siguiente problema: dado un gráfico de consulta y un gráfico de referencia , queremos encontrar el mapeo inyectivo que minimiza el número de bordes tal que . Esta es una generalización del problema del isomorfismo del subgrafo en el que permitimos que los subgrafos sean isomorfos hasta...
El algoritmo Weisfeiler-Lehman 1-dim (WL) se conoce comúnmente como etiquetado canónico o algoritmo de refinamiento de color. Funciona de la siguiente manera: La coloración inicial es uniforme, C 0 ( v ) = 1 para todos los vértices v ∈ V ( G ) ∪ V ( H ) .C0 0C0 0C_0C0 0( v ) = 1C0 0(v)=1C_0(v) =...
El isomorfismo gráfico ( ) es un buen candidato para el intermedio . : existen problemas intermedios a menos que . Estoy buscando un problema natural que sea difícil para bajo la reducción de Karp (un problema de gráfico tal que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
GI y Knot Problem, ambos son problemas para decidir la equivalencia estructural de los objetos matemáticos. ¿Hay algún resultado que establezca conexiones entre ellos? Se han explorado buenas conexiones del problema de nudos con la física estadística a través de polinomios de nudos , ¿hay...
Estoy revisando un modelo criptográfico. Para mostrar su insuficiencia, he diseñado un protocolo artificial basado en el isomorfismo gráfico. Es "común" (¡pero controvertido!) Asumir la existencia de algoritmos BPP capaces de generar "instancias difíciles del problema del isomorfismo gráfico"....
Dado un grupo solGG de permutaciones en [ n ] = { 1 , ⋯ , n }[n]={1,⋯,n}[n]=\{1, \cdots, n\} y dos vectores u , v ∈ Γnorteu,v∈Γnu,v\in \Gamma^n donde ΓΓ\Gamma es un alfabeto finito que no es del todo relevante aquí, la pregunta es si existe algún π∈ Gπ∈G\pi\in G tal que π( u ) = vπ(u)=v\pi(u)=v...
Tengo una pregunta (con suerte simple, tal vez tonta) en el documento histórico de Babai que muestra que es cuasipolinomial.GIGI\mathsf{GI} Babai mostró cómo producir un certificado de que dos gráficas para i ∈ { 1 , 2 } son isomorfas, en el tiempo cuasipolinomiales en v = | V i |...
Durante la lectura de las preguntas ejemplos donde la unicidad de la solución hace que sea más fácil encontrar , una nueva (? Más fácil) pregunta vino a la mente: en realidad no sabemos si el isomorfismo de grafos ( problema) está en P .G IsolyoGIPAGPAGP Pero, ¿qué sucede si suponemos que tanto...
Quiero ser muy específico ¿Alguien sabe de una prueba o prueba de la siguiente propuesta: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in STRUC[\Sigma_{graph}]...
¿Qué otros problemas de idiomas diferentes al isomorfismo de gráficos hay en ? ¿Puedes dar algunas referencias?nortePAG∩ c o A MNP∩coAMNP\cap coAM Actualización: Olvidé mencionar que estoy interesado en idiomas que no se sabe que están en .c o
Imaginemos que tenemos dos conjuntos de puntos tamaño . ¿Cuál es la complejidad (temporal) de las pruebas si difieren solo por rotación? : existe una matriz de rotación tal que ?mmm O O T = O T O = I X = O YX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Hay un...
En el famoso contraejemplo para el isomorfismo gráfico mediante el método Weisfeiler-Lehman (WL) , Cai, Furer e Immerman construyeron el siguiente dispositivo en este documento . Construyen un gráfico dado porXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k,
Se han realizado algunos esfuerzos para atacar el problema del isomorfismo gráfico utilizando la caminata aleatoria cuántica de bosones de núcleo duro (simétrica pero sin ocupación doble). Amir Rahnamai Barghi e Ilya Ponomarenko demostraron que el poder simétrico de la matriz de adyacencia, que...
Estoy interesado en estudiar los problemas completos del isomorfismo gráfico (IG). En el documento "Problemas polinomialmente equivalentes al isomorfismo gráfico" de Kellogg S. Booth, (1979), demostró que muchos problemas básicos se completan GI mediante el uso de técnicas de reemplazo de bordes,...
Parte de la dificultad de obtener más información sobre este problema es que el problema de coincidencia de gráficos es diferente de su primo mucho más famoso, el problema de coincidencia, pero es difícil distinguirlo cuando se utilizan motores de búsqueda. Dados dos gráficos y modo que, la tarea...
Me gustaría preguntar si hay un resultado ya publicado sobre eso: Tomamos todos los caminos diferentes posibles entre cada par de nodos de dos gráficos regulares conectados (con el grado , digamos, y el número de nodos n ) y escribimos sus longitudes. Por supuesto, este número de caminos distintos...
Dado cualquier gráfico G no dirigido simple, no es trivial determinar si G tiene automorfismos no triviales (no identitarios). Pero, ¿cuáles son los resultados en los límites superior / inferior de este problema de
¿El problema de isomorfismo de semigrupo inverso finito es GI completo ? Aquí se supone que los semigrupos inversos finitos están dados por sus tablas de