TY - JOUR

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

AU - Shizuya, Hiroki

AU - Itoh, Toshiya

PY - 1994/1

Y1 - 1994/1

N2 - 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 Δ2P 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 Δ2P 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 DP. Here DP 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.

AB - 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 Δ2P 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 Δ2P 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 DP. Here DP 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.

UR - http://www.scopus.com/inward/record.url?scp=0028196051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028196051&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0028196051

SN - 0916-8508

VL - E77-A

SP - 65

EP - 71

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 1

ER -