A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
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 △^2⋂ AM ⋂ co-AM but is unlikely to be in NP ⋃ co-NP, and that GH is in △^2⋂ 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
- 社団法人電子情報通信学会の論文
- 1994-01-25
著者
-
Itoh Toshiya
Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology
-
Shizuya Hiroki
Education Center For Information Processing Tohoku University
-
Shizuya Hiroki
Education Center For Information Processing And Graduate School Of Information Sciences Tohoku Unive
関連論文
- Checkers for Adaptive Programs
- Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing
- A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
- A Note on the Complexity of Breaking Okamoto-Tanaka ID-Based Key Exchange Seheme (Special Section on Cryptography and Information Security)
- Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
- On the Complexity of the Discrete Logarithm for a General Finite Group (Special Section on Cryptography and Information Security)
- On the Σ^b_1-Definability of Integer Factoring
- On the Security of the Okamoto-Tanaka ID-Based Key Exchange Scheme against Active Attacks
- On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)
- On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)
- Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)
- On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)
- On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)