The formula isomorphism problem

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