ECCC-Report TR96-032https://eccc.weizmann.ac.il/report/1996/032Comments and Revisions published for TR96-032en-usMon, 13 May 1996 16:45:02 +0300
Paper TR96-032
| The Boolean Isomorphism Problem |
Manindra Agrawal,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/1996/032 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 $\overline{BI}$, where the Verifier
has access to an NP oracle. To obtain this, we use a recent 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, BI cannot be $\Sigma_2^p$ complete
unless the Polynomial Hierarchy collapses. This solves an open problem posed in Borchert
et.al.
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.
Mon, 13 May 1996 16:45:02 +0300https://eccc.weizmann.ac.il/report/1996/032