The Complexity Landscape of Boolean Formula Isomorphism: From Graph Isomorphism to the Second Level

Abstract This paper studies the isomorphism problem for Boolean formulas and places it precisely in the polynomial hierarchy. Two of its results are new. The first sharpens the relationship between Boolean and graph isomorphism. Chang's reduction shows only that the unrestricted Boolean isomorphism problem is \(\mathrm{GI}\)-hard, in one direction; restricting both inputs to canonical form, where equivalence is free, sharpens this to a both-directions many-one equivalence. Encoding each input as a weight-two-minterm canonical \(\mathrm{DNF}\) rigid enough that every renaming witnessing isomorphism is forced to be a graph isomorphism, we obtain Canonical Formula Isomorphism \(\mathrm{CFI} \equiv _{m}\) \(\mathrm{GI}\), together with \(\mathrm{CFNI} \equiv _{m}\) \(\mathrm{GNI}\) for the separation problem. This is completeness in both directions, not the one-directional hardness Chang established. The second result is a classification instrument: writing formula isomorphism as \(\mathrm{FI} = \exists \lambda \cdot \mathrm{EQ}\) exhibits the renaming as a single existential quantifier over a polynomial-size witness applied to the equivalence problem of the inputs, so the renaming is the only complexity the isomorphism question adds beyond equivalence, and the equivalence cost caps the level and fixes its semantic component, while the renaming search supplies the residual structural complexity, which on canonical inputs is exactly the graph-isomorphism core above. Applying the instrument to compact representations, where equivalence is \(\mathrm{coNP}\)-complete, places the mixed case \(\mathrm{DT\text{-}FI}\) (an arbitrary formula matched against a \(\mathrm{DNF}\) target) and the fully compact case \(\mathrm{CNF\text{-}FI}\) at the second level: both lie in \(\Sigma _{2}^{P}\), are \(\mathrm{coNP}\)-hard and \(\mathrm{GI}\)-hard, and are complete for no level unless the polynomial hierarchy collapses. The structural facts that frame this level (Sch"oning's lowness \(\Sigma _{k}^{P}[\mathrm{GI}] = \Sigma _{k}^{P}\) for k \(\geq \) 2, under which a graph-isomorphism oracle adds nothing at the second level and above; a first-level boundary at which the graph-isomorphism level lies in \(\mathrm{NP} \cap \mathrm{coNP}\) exactly when \(\mathrm{GI}\) is low for \(\mathrm{NP}\); and a conditional non-completeness from \(\mathrm{GI} \in \mathrm{coAM})\) are not new, and the paper's role for them is to combine them into a four-case analysis of when the graph-isomorphism core can affect the hierarchy: only when it is complete for its level, and then only at the second. In every case the residue that remains once the equivalence test is made free is graph isomorphism itself.