On zero error algorithms having oracle access to one query
On zero error algorithms having oracle access to one query
复制标题
关于 Oracle 访问一个查询的零错误算法
DOI：
--
复制
发表时间：
2006
影响因子：
1
通讯作者：
Venkatesan T. Chakaravarthy
中科院分区：
文献类型：
--
作者：
Jin;Venkatesan T. Chakaravarthy
据了解，$${
m S}_{2}^{p} 子集eq {
m ZPP}^{NP}$$（蔡，2001）。 $${中是否包含ZPPNP的反方向
m S}_{2}^{p}$$ 保持开放状态。我们证明，如果零错误算法只允许向 NP 预言机询问一次查询（对于任何输入和随机字符串），那么它可以在 $${
m S}_{2}^{p}$$。也就是说，我们证明$${
m S}_{2}^{p}$$。接下来我们考虑上面的结果是否可以改进为$${
m ZPP}^{NP[1]} 子集eq {
m P}^{NP}$$ 并指出这样做的困难。通过简单的证明，我们观察到 BPP ⊆ ZPPNP[1]（在一些先前的工作中隐式证明的结果）。因此，实现上述改进将意味着 BPP ⊆ PNP，解决了一个长期悬而未决的问题。然后我们认为，上述改进可以在多项式时间层次结构的下一个级别获得。也就是说，我们证明$${
m ZPP}^{Sigma_{2}^{p}[1]} 子集eq {
m P}^{Sigma_{2}^{p}[2]}$$。另一方面，通过调整我们的主要结果证明，可以证明 $${
m ZPP}^{Sigma_{2}^{p}[1]} 子集eq {
米S}_{2}^{
m NP[1]}$$。为了比较这两个结果，我们证明 $${
m P}^{Sigma_{2}^{p}} 子集eq {
米S}_{2}^{
m NP[1]}$$。我们通过观察得出结论，上述主张扩展到了层次结构的更高级别：对于 k ≥ 2，$${
m ZPP}^{Sigma_{k}^{p}[1]} 子集eq {
m P}^{Sigma_{k}^{p}[2]}$$ 和 $${
m P}^{Sigma_{k}^{p}} 子集eq {
m S}_{2}^{Sigma_{k-1}^{p}[1]}$$。
It is known that $${
m S}_{2}^{p} subseteq {
m ZPP}^{NP}$$ (Cai, 2001). The reverse direction of whether ZPPNP is contained in $${
m S}_{2}^{p}$$ 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 $${
m S}_{2}^{p}$$. That is, we prove that $${
m S}_{2}^{p}$$. Next we consider whether the above result can be improved as $${
m ZPP}^{NP[1]} subseteq {
m P}^{NP}$$ and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPPNP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ PNP, settling a long standing open problem.We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that $${
m ZPP}^{Sigma_{2}^{p}[1]} subseteq {
m P}^{Sigma_{2}^{p}[2]}$$. On the other hand, by adapting our proof of our main result it can be shown that $${
m ZPP}^{Sigma_{2}^{p}[1]} subseteq {
m S}_{2}^{
m NP[1]}$$. For the purpose of comparing these two results, we prove that $${
m P}^{Sigma_{2}^{p}} subseteq {
m S}_{2}^{
m NP[1]}$$. We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2,$${
m ZPP}^{Sigma_{k}^{p}[1]} subseteq {
m P}^{Sigma_{k}^{p}[2]}$$ and $${
m P}^{Sigma_{k}^{p}} subseteq {
m S}_{2}^{Sigma_{k-1}^{p}[1]}$$.