2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

• 10.7k

### What evidence is there that Graph Isomorphism is not in $P$?

The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than $n!$ but still exponential, OEIS A186202. The number of bits ...
• 2,331

### Complexity of permutation related problems

Your problem is known as ($\Gamma$-)string $G$-isomorphism. It is in a fairly narrow class of problems around Graph Isomorphism: it's at least as hard as GI, and is in $\mathsf{NP} \cap \mathsf{coAM}$....
• 35.6k
Accepted

### Connections between Graph Isomorphism and Polynomial Equivalence

The paper you linked in the comments - and references therein - already seems to answer your first question. For your second question: I have little reason to think that there is a theorem of the ...
• 35.6k

Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in this answer, testing whether $g \in \langle g_1, \ldots, g_k\rangle$ is in $\text{... • 2,512 9 votes Accepted ### Graph isomorphism with equivalence relation on the vertex set The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any ... • 35.6k 9 votes Accepted ### Is the finite inverse semigroup isomorphism problem GI-complete? Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of Theorem: Lattice isomorphism is isomorphism complete from section 7.2 Lattices and Posets in Booth, ... • 3,013 9 votes Accepted ### Number of Automorphisms of a graph for graph isomorphism Wormald has shown that if$G$is a connected$3$-regular graph with 2n vertices then the number of automorphisms of$G$divides$3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-... 9 votes ### What evidence is there that Graph Isomorphism is not in$P$? Kozen in his paper, A clique problem equivalent to graph isomorphism, gives an evidence that$GI$is not in$P$. The following is from the paper: "Nevertheless, it is likely that finding a ... 9 votes Accepted ### For any two non-isomorphic graphs$G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this? Thanks to my colleague Maxim Zhukovskii for suggesting this answer. It turns out that the answer is negative, and the counterexample is rather simple. Just take$G=K_m\sqcup \overline{K_m}$and$H=K_{...
Only an extended comment: Lipton et al. proved [1] that if we have access to an oracle that given two graphs on $n$ vertices, reveals a partial map on at least $(3+\epsilon)\log n$ vertices (for some ...