A Note on AM Languages Outside NP <cd02240.gif> co-NP

Hiroki SHIZUYA; Toshiya ITOH

A Note on AM Languages Outside NP co-NP

Hiroki SHIZUYA, Toshiya ITOH

Full Text Views

0

Share
Cite this

Summary :

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 Δ^P₂ AM co-AM but is unlikely to be in NP co-NP, and that GH is in Δ^P₂ 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 D^P. Here D^P is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.1 pp.65-71

Publication Date: 1994/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Hiroki SHIZUYA, Toshiya ITOH, "A Note on AM Languages Outside NP co-NP" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 1, pp. 65-71, January 1994, doi: .
Abstract: 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 Δ^P₂ AM co-AM but is unlikely to be in NP co-NP, and that GH is in Δ^P₂ 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 D^P. Here D^P is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e77-a_1_65/_p

Copy

@ARTICLE{e77-a_1_65,
author={Hiroki SHIZUYA, Toshiya ITOH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on AM Languages Outside NP co-NP},
year={1994},
volume={E77-A},
number={1},
pages={65-71},
abstract={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 Δ^P₂ AM co-AM but is unlikely to be in NP co-NP, and that GH is in Δ^P₂ 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 D^P. Here D^P is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - A Note on AM Languages Outside NP co-NP
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 65
EP - 71
AU - Hiroki SHIZUYA
AU - Toshiya ITOH
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1994
AB - 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 Δ^P₂ AM co-AM but is unlikely to be in NP co-NP, and that GH is in Δ^P₂ 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 D^P. Here D^P is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.
ER -