CJTCS Volume 1998 Article 1

The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits

Thomas Thierauf (Universität Ulm) 10 March 1998 Special Issue on Computational Complexity from the 1996 Dagstuhl-Seminar, Eric Allender editor

Abstract

We investigate the computational complexity of the isomorphism problem for read-once branching programs (1-BPI): upon input of two read-once branching programs B_0 and B_1, decide whether there exists a permutation of the variables of B_1 such that it becomes equivalent to B_0.

Our main result is that 1-BPI cannot be NP-hard unless the polynomial hierarchy collapses. The result is extended to the isomorphism problem for arithmetic circuits over large enough fields.

We use the known arithmetization of read-once branching programs and arithmetic circuits into multivariate polynomials over the rationals. Hence, another way of stating our result is: the isomorphism problem for multivariate polynomials over large enough fields is not NP-hard unless the polynomial hierarchy collapses.

We derive this result by providing a two-round interactive proof for the nonisomorphism problem for multivariate polynomials. The protocol is based on the Schwartz-Zippel theorem for probabilistically checking polynomial identities.

Finally, we show that there is a perfect zero-knowledge interactive proof for the isomorphism problem for multivariate polynomials.

• Preformatted versions of the article
  • DVI (89,724 bytes)
  • PostScript (419,197 bytes)
  • PDF (336,857 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj98-01.tex , 59,695 bytes)
  • BIBTeX ( cj98-01.bib , 7,514 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 164 bytes)
  • Self citation in BIBTeX (288 bytes)
• Online discussion
• Instructions for Readers

---

Volume 1997, Article 5 Article 2
Volume 1998 Published articles

Last modified: Mon Aug 10 12:03:32 CDT