Isomorfismo de gráfico “minúsculo”

Enquanto pensava na complexidade de testar o isomorfismo de gráficos assimétricos (veja minha pergunta relacionada à história), uma pergunta complementar veio à minha mente.

Suponha que temos uma máquina de Turing polinomial de tempo que, na entrada gera um gráfico com nós.1 n G M , n$M$$1^n$$G_{M,n}$$n$

Podemos definir o problema :$\Pi_M$

(GI "minúsculo"): Dado um gráfico , é isomórfico para ?G G M , | V $G=(V,E)$$G$$G_{M,|V|}$

Em outras palavras, deve comparar um dado gráfico com um gráfico de "referência" do mesmo tamanho gerado por um tempo polinomial máquina de Turing fixo .$M$

Por todo o tempo Turing máquinas polinomiais , temos e, para muitos deles, temos . Mas é verdade para todos os ? O problema é conhecido?Π M ∈ N P Π M ∈ P $M$$\Pi_M \in NP$$\Pi_M \in P$
$M$

À primeira vista, pensei que todo deveria ser muito mais fácil que o , porque para todo existe apenas um gráfico de "referência" desse tamanho e talvez as simetrias / assimetrias dos gráficos gerados por possam ser exploradas e um testador de isomorfismo ad-hoc pode ser construído ... mas não é verdade: pode conter algum tipo de máquina Universal Turing com sincronização polinomial que usa a entrada (unária) para gerar gráficos de referência completamente diferentes (na estrutura) como aumenta. G I n M M 1 n$\Pi_M$$GI$$n$$M$$M$$1^n$$n$

[Este é mais alguns comentários estendidos do que uma resposta.]

1) Se , então não há fixo-polinomial ligado na complexidade de tempo de todos Π M , mesmo para M que apenas levam tempo, digamos, n 3 : Se para todos tempo- n 3 H , Π M ∈ D T I M E ( n k ) , a seguir é apresentado um algoritmo poli-tempo para GI. Na entrada ( G , H ) , construa uma máquina de Turing M G com um relógio que garanta que M $GI \notin \mathsf{P}$$\Pi_{M}$$M$$n^3$$n^3$ $M$$\Pi_{M} \in \mathsf{DTIME}(n^k)$$(G, H)$$M_{G}$$M_{G}$nunca é executado por mais de etapas em entradas de tamanho n e de modo que M G ( 1 | V ( G ) | ) = G e depois resolva Π M G ( H ) no tempo O ( n k ) .$n^3$$n$$M_{G}(1^{|V(G)|}) = G$$\Pi_{M_G}(H)$$O(n^k)$

2) Como para qualquer , Π M não é mais difícil que GI, pode-se pensar que o melhor resultado na linha de " Π M parece não estar em P " que se poderia esperar é um resultado de completude GI. No entanto, parece-me improvável que qualquer um Π M seja GI completo, pelo menos pelos seguintes motivos:$M$$\Pi_{M}$$\Pi_M$$\mathsf{P}$$\Pi_M$

• Todos os resultados de integridade GI que conheço são para classes bastante grandes de gráficos, em vez de ter um único gráfico de cada tamanho. Mesmo que você abandone completamente o requisito de eficiência, não conheço nenhuma lista de gráficos modo que | V ( L n ) | = N (ou mesmo p o l y ( n ) ) de tal modo que a testar isomorfismo para G n é GI-completo.$G_1, G_2, \dotsc$$|V(G_n)| = n$$poly(n)$$G_n$

• Em uma nota relacionada, a maioria dos resultados (todos?) De completude GI não é apenas uma redução de muitas, mas tem a seguinte forma: existe uma função tal que, dada uma instância ( G , H ) de GI, ( f ( G ) , f ( H ) ) é instância do outro problema de GI completo. (Estes são apenas morfismos polivalentes das relações de equivalência, ou o que Fortnow e eu chamamos de "reduções do kernel.) Podemos facilmente mostrar incondicionalmente que não há tal redução de GI para nenhum Π M (mesmo se você modificar a definição para permitir $f$$(G,H)$$(f(G), f(H))$$\Pi_M$$M$para gerar vários gráficos). Dica: Obtenha uma contradição, mostrando que qualquer um desses deve ter sua imagem completamente contida em { G M , n } n ≥ 0 .$f$$\{G_{M,n}\}_{n \geq 0}$

3) Embora se possa construir base em uma TM universal, como sugerido na pergunta, talvez ainda seja possível construir um testador eficiente, mas não de maneira eficiente. Isto é, talvez para cada um H , Π M é em P / p o l y ?$M$$M$$\Pi_{M}$$\mathsf{P/poly}$

Não tenho resposta para sua pergunta, mas proponho considerar uma versão mais restrita de para a qual podemos mostrar que ela está em P.$\Pi_M$

Vamos considerar apenas famílias de gráficos de tal forma que o número de arestas cresça logaritmicamente. Eu formalizarei isso reformulando sua formulação do problema, também para ver se entendi corretamente.

Um gráfico não direcionado com n arestas pode ser descrito por um n 2 - $G$$n$ bit de cadeia longa, basta concatenar as entradas da matriz de adjacência deGno triângulo superior. Portanto, existem2 n 2 - $\frac{n^2-n}{2}$$G$ gráficos possíveis emnvértices. Segue-se que qualquer funçãof:N→Ntal que0≤f(n)<2n2-$2^{\frac{n^2-n}{2}}$$n$$f : \mathbb{N} \rightarrow \mathbb{N}$ para todos osndescreve uma família de gráficos. Para qualquer função eficientemente computávelfdefinimosΠfcomo G∈Π$0 \leq f(n) < 2^{\frac{n^2-n}{2}}$$n$$f$$\Pi_f$

Para um número natural seja b 1 ( x ) o número de 1's em sua representação binária. Agora, vamos considerar apenas Π f para funções eficientemente computáveis f para as quais ele sustenta que b 1 ( f ( n ) ) ∈ O ( log n ) que é uma família de gráficos para os quais o número de arestas cresce apenas logaritmicamente, conforme declarado acima .$x$$b_1(x)$$\Pi_f$$f$

Mostramos que para esta classe de funções está em P.$\Pi_f$

Seja uma função e G seja um gráfico de entrada com n vértices. Vamos chamar f ( n ) o gráfico de referência. Existem no máximo arestas O ( log n ) no gráfico de referência. Assim, todo MCC (componente conectado maximamente) pode consistir em no máximo O ( log n ) vértices dos quais pode haver no máximo n . Note-se, que para qualquer par de gráficos com apenas ó ( log n ) vértices podemos verificar trivialmente isomorfismo em tempo polynomialy wrt $f$$G$$n$$f(n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$n$$\mathcal{O}(\log n)$$n$porque podemos tentar todas as permutações. Assim, usando um algoritmo guloso para atribuir a cada MCC do gráfico de entrada uma MCC no gráfico de referência, podemos descobrir se os dois gráficos são isomorfos.