Is boolean formula isomorphism NP-complete?

Problem. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as number of total assignments is bounded by exponent).

Example. $f=(x\land y\land z)\lor(\overline x\lor z)$. $g=(x\lor\overline y)\land(x\lor y\lor z)$.

Replacing $x$ and $y$ in $g$: $g = (\overline x\lor y)\land(x\lor y\lor z)$.

Replacing $y$ and $z$ in $g$: $g = (\overline x\lor z)\land(x\lor y\lor z)$. It became equal to $f$.

While this is considered not to be $\mathsf{NP}$-complete for 2SAT (we can compare their implication graphs and this is GI), is this problem $\mathsf{NP}$-complete for other variants of SAT (Horn3SAT, XOR3SAT, unambiguos 3SAT; if not, then at least 3SAT)?

Also there are two variations of problem:

• All clauses in formula become equal (but in this case number of non-isomorphic functions is superexponential).

• Number of satisfying assignments is equal (don't suspect to be in $\mathsf{NP}$ except for 2SAT; and it is $\mathsf{NP}$-hard for 3SAT).

Your problem is $\mathrm{co}$-$\mathrm{NP}$-hard so it may also be $\mathrm{NP}$-hard but very unlikely to be $\mathrm{NP}$-complete (i.e. to be in $\mathrm{NP}$).

We reduce from TAUT which is $\mathrm{co}$-$\mathrm{NP}$-hard. Given a TAUT instance $\varphi$ with variables $x_1,\dots x_n$, output $$. These two formulae are isomorphism iff. $\varphi$ is a tautology.

StackExchange Computer Science Q#80530, answer score: 2