The boolean isomorphism problem

Agrawal, M. ; Thierauf, T. (1996) The boolean isomorphism problem Proceedings of IEEE 37th Annual Symposium on Foundations of Computer Science . pp. 422-430. ISSN 0272-5428

Full text not available from this repository.

Official URL:

Related URL:


We investigate the computational complexity of the Boolean isomorphism problem (BI): 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. Our main result is a one-round interactive proof for BI, where the verifier has access to an NP oracle. To obtain this, we use a recent result from learning theory by N. Bshouty et al. (1995), that Boolean formulas can be learned probabilistically with equivalence queries and access to an NP oracle. As a consequence, BI cannot be Σ2p complete unless the polynomial hierarchy collapses. This solves an open problem posed previously. Further properties of BI are shown: BI has And- and Or-functions, the counting version, BI, can be computed in polynomial time relative to BI, and BI is self-reducible.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:95348
Deposited On:07 Nov 2012 05:31
Last Modified:07 Nov 2012 05:31

Repository Staff Only: item control page