We investigate the computational complexity of the

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
to probabilistically check polynomial identities.

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