The formula isomorphism problem

Abstract

We investigate the computational complexity of the formula isomorphism problem (FI): on input of two boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. FI is contained in Σ₂ P, the second level of the polynomial hierarchy. Our main result is a one-round interactive proof for the complementary formula nonisomorphism problem (FNI), where the verifier has access to an NP-oracle. To obtain this, we use a result from learning theory by Bshouty et al. that boolean formulas can be learned probabilistically with equivalence queries and access to an NP-oracle. As a consequence, FI cannot be Σ₂ P-complete unless the polynomial hierarchy collapses. Further properties of FI are shown: FI has and- and or-functions, the counting version, #FI, can be computed in polynomial time relative to FI, and FI is self-reducible.