Note on AM languages outside NP and the union of all the sets co-NP

In this paper we investigate the AM languages that seem to be located outside NP and the union of all the sets 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 Δ₂^P in the intersection of all the sets AM and the intersection of all the sets co-AM but is unlikely to be in NP and the union of all the sets co-NP, and that GH is in Δ₂^P in the intersection of all the sets AM but is unlikely to be in NP and the union of all the sets 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 in the intersection of all sets co-AM; GIP is in co-SZK if SZK in the intersection of all the sets co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in D^P. Here D^P is the class of languages that can be expressed in the form X in the intersection of all sets Y, where X ∈ NP and Y ∈ co-NP.