A Note on Zero Error Algorithms Having Oracle Access to One NP Query

摘要：

It is known that SP2 (∪) ZPPNP 3. The reverse direction of whether ZPPNP is contained in SP2 remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in SP2.That is, we prove that ZPPNP1 (∪) SP2.

作者: Jin-Yi Cai Venkatesan T. Chakaravarthy

作者单位: Computer Science Department, Univ. of Wisconsin, Madison, WI 53726, USA Tsinghua University, Beijing IBM India Research Lab, IIT Campus, New Delhi 110016, India

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 339-348

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）