Two candidates for NP-hardness of isomorphism are CIRCUIT ISOMORPHISM and FORMULA ISOMORPHISM.
For CIRCUIT ISOMORPHISM Joshua Grochow claims.
Circuit Isomorphism is the problem: given two circuits $C_1, C_2$ on $n$ inputs, is there a permutation $\pi \in S_n$ such that $C_1(\vec{x})$ and $C_2(\pi(\vec{x}))$ are equivalent? Circuit Isomorphism has a status similar to that of Graph Isomorphism, but one level higher in $\mathsf{PH}$: it is $\mathsf{coNP}$-hard (by the same reduction above), not known to be in $\mathsf{coNP}$, in $\mathsf{\Sigma_2 P}$, but not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH} = \mathsf{\Sigma_3 P}$
For FORMULA ISOMORPHISM: Michael Bauland, Edith Hemaspaandra, Isomorphic Implication, Theory Comput Syst (2009) 44: 117–139, doi:10.1007/s00224-007-9038-1, arXiv:Isomorphic Implicationcs/0412062, on p.1:
On p.1: TheThe formula isomorphism problem is in $\Sigma_2^p$ , NP-hard, and unlikely to be $\Sigma_2^p$.-complete
From the abstract:
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in parallel access to NP. We show how to extend the NP-hardness and coNP-hardness to hardness for parallel access to NP for some cases, and conjecture that this can be done in all cases.
These examples appear to contradict Emil's claim that isomorphism of finite object can't be too hard.
