structural equivalence of boolean functions and the graph isomorphism problem

One of the important problems for synthesis and verification of Boolean circuits is:
if two Boolean functions are equivalent.

Two booleans functions of the same arity are equivalent if they map the same values into the same values.
It is well known that this formula is NP-complete in respect to the size of the Boolean function representation.

Consider another problem STRUCTURAL EQUIVALENCE of BOOLEAN FUNCTIONS:
given the representation of two Boolean functions as propositional formulae \Psi_1 and \Psi_2: is there exist a mapping from from variables \Psi_1 to variables of \Psi_2 with transposing o 1nd 1 states at any lead such that the formalue will be syntactically equivalent.

Or two Boolean function representations are on the same orbit of the group generated by permutation and complementations of the variables

Basicaly it means:
given two circuit descriptions, do they represent the same physically circuit?

The complexity of this problem is not known, it is know that this problem is equivalent to the GI Graph Isomorphism problem.


Babai Luks algorithm for GI runs in O(c^n^{1/2})
For graphs of genus \leq g, the GI can be solved in O(n^{O(g)})
It is known (as a consequence of Bodlaender theorem), that for graphs with a bounded tree-width GI can be solved in polynomial time.


Let Aug(G) denote the automorphism group of G
The following problems are PTIME equivalent

1. Graph Isomorphism
2. Graph Isomorphism Counting (the number of isomorphism from G to H)
3. Complement Isomorphism: If G is isomorphic to its compliment
4. Generating Set for Aut(g): determine a generating set for Aut(G)
5. context-free grammar isomorphism
6. conjuctive-query isomorphism
   

There is an evidence that GI is not NP-hard. Bopanna, HAstad, Zachos has shown (1982) that if the GI is N P-hard then polynomial hierarchy collapes to \Pi^p_2