The formula isomorphism problem

Agrawal, Manindra ; Thierauf, Thomas (2000) The formula isomorphism problem SIAM Journal on Computing, 30 (3). pp. 990-1009. ISSN 0097-5397

Full text not available from this repository.

Official URL:

Related URL:


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 Σ2 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 Σ2 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.

Item Type:Article
Source:Copyright of this article belongs to Society for Industrial & Applied Mathematics.
Keywords:Boolean Isomorphism Problems; Complexity Theory; Interactive Proofs; Learning Theory
ID Code:20241
Deposited On:20 Nov 2010 14:48
Last Modified:20 Nov 2010 14:48

Repository Staff Only: item control page