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: http://link.aip.org/link/?SMJCAT/30/990/1

Related URL: http://dx.doi.org/10.1137/S0097539798343647

## Abstract

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