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: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnum...
Related URL: http://dx.doi.org/10.1109/SFCS.1996.548501
Abstract
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