Arthur and Merlin as Oracles期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

首页 | 本学科首页

官方微博 | 高级检索

Arthur and Merlin as Oracles

Authors:

Venkatesan T Chakaravarthy Sambuddha Roy

Affiliation:

1. IBM Research Lab, New Delhi, India

Abstract:

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin class. Our main results are the following:

° BPP^NP_\|\| í P^prAM_\|\|.\circ\quad{\rm BPP}^{{\rm NP}}_{\|\|} \subseteq {{\rm P}^{{{\rm pr}{\rm AM}}}_{\|\|}}.

Keywords:
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏