Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin game). Unfortunately, the applicability of their transformation to cryptography is limited because it does not preserve the computational complexity of the prover's strategy. Vadhan showed that this deficiency is inherent by constructing a promise problem Π with a private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time with oracle access to the original prover. However, the transformation formulated by Vadhan has a restriction, i.e., it does not allow the new prover and verifier to look at common input. This restriction is essential for the proof of Vadhan's negative result. This paper considers an unrestricted transformation where both the new prover and verifier are allowed to access and analyze common input. We show that an analogous negative result holds even in this unrestricted case under a non-standard computational assumption.

In this paper we investigate the AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.