The Boolean Isomorphism Problem

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 /spl Sigma//sub 2//sup p/ 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.

Authors

• Manindra Agrawal
• Thomas Thierauf

Keywords

• Bismuth
• Polynomials
• Circuits
• Computer science
• Computational complexity
• Computational modeling
• Context modeling
• Turing machines
• Binary decision diagrams
• Boolean functions
• Isomorphism Problem
• Permutation
• New Variables
• Affine Transformation
• Normal Form
• Partial Order
• Internet Protocol
• Boolean Function
• Vector C
• Counter Example
• Set Of Formulas
• Graph Isomorphism
• Probabilistic Polynomial Time
• Input Circuit
• Linear Equivalent