The Isomorphismproblem for One-Time-Only Branching Programs
Thomas Thierauf · 1996
We investigate the computational complexity of the isomorphism problem for one-timeonly branching programs (BP1-Iso): on input of two one-time-only 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 a two-round interactive proof for BP1-Iso, the complement of BP1-Iso. The protocol is based on the Schwartz-Zippel Theorem to probabilistically check polynomial idendities. As a consequence, BP1-Iso cannot be NP hard unless the polynomial hierarchy collapses. We extend the protocol to get an interactive proof to decide the non-isomorphism of multivariate polynomials over an arbitrary field. Finally, we show that BP1-Iso has a zero-knowledge interactive proof. 1 Introduction An interesting computational issue is to decide the equivalence of two given programs with respect to some computational model as, for example, Boolean circuits, branching programs, or Boolean formulas. A more ge...