\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs.

*(English)*Zbl 0802.68054Summary: We show that \(BPP\) can be simulated in subexponential time for infinitely many input lengths unless exponential time

\(\circ\) collapses to the second level of the polynomial-time hierarchy,

\(\circ\) has polynomial-size circuits, and

\(\circ\) has publishable proofs \((EXPTIME = MA)\).

We also show that \(BPP\) is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, we show \(BPP\) can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in \(MA\)-\(P\).

The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low-degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.

One of the ingredients of our proof is a lemma that states that if \(EXPTIME\) has polynomial size circuits then \(EXPTIME=MA\). This extends previous work by A. Meyer.

\(\circ\) collapses to the second level of the polynomial-time hierarchy,

\(\circ\) has polynomial-size circuits, and

\(\circ\) has publishable proofs \((EXPTIME = MA)\).

We also show that \(BPP\) is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, we show \(BPP\) can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in \(MA\)-\(P\).

The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low-degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.

One of the ingredients of our proof is a lemma that states that if \(EXPTIME\) has polynomial size circuits then \(EXPTIME=MA\). This extends previous work by A. Meyer.

##### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

PDF
BibTeX
XML
Cite

\textit{L. Babai} et al., Comput. Complexity 3, No. 4, 307--318 (1993; Zbl 0802.68054)

Full Text:
DOI

##### References:

[1] | L. Adleman, Two theorems on random polynomial time, inProceedings of the 19th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1978, 75-83. |

[2] | L. Babai, Trading group theory for randomness, inProceedings of the 17th ACM Symposium on the Theory of Computing, ACM, New York, 1985, 421-429. |

[3] | L. Babai andL. Fortnow, Arithmetization: A new method in structural complexity theory,Computational Complexity,1:1 (1991), 41-66. · Zbl 0774.68040 |

[4] | L. Babai, L. Fortnow, andC. Lund, Non-deterministic exponential time has two-prover interactive protocols,Computational Complexity,1:1 (1991), 3-40. · Zbl 0774.68041 |

[5] | L. Babai andS. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes,Journal of Computer and System Sciences,36:2 (1988), 254-276. · Zbl 0652.03029 |

[6] | D. Beaver andJ. Feigenbaum, Hiding instances in multioracle queries, inProceedings of the 7th Symposium on Theoretical Aspects of Computer Science, volume 415 ofLecture Notes in Computer Science, Springer, Berlin, 1990, 37-48. |

[7] | M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson, Multiprover interactive proofs: How to remove intractability assumptions, inProceedings of the 20th ACM Symposium on the Theory of Computing, ACM, New York, 1988, 113-131. |

[8] | C. Bennet andJ. Gill, Relative to a random oracle,P A ? NPA ? co-NPA with probability one,SIAM Journal on Computing,10 (1981), 96-113. · Zbl 0454.68030 |

[9] | M. Blum and S. Kannan, Designing programs that check their work, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 86-97. · Zbl 0886.68046 |

[10] | M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs, with applications to numerical programs, inProceedings of the 22nd ACM Symposium on the Theory of Computing, ACM, New York, 1990, 73-83. |

[11] | M. Blum andS. Micali, How to generate cryptographically strong sequences of pseudo-random bits,SIAM Journal on Computing,13 (1984), 850-864. · Zbl 0547.68046 |

[12] | R. Boppana andR. Hirschfeld, Pseudorandom generators and complexity classes, inRandomness and Computation, volume 5 ofAdvances in Computing Research, S. Micali, ed., JAI Press, Greenwich, 1989, 1-26. |

[13] | O. Goldreich, H. Krawczyk, and M. Luby, On the existence of pseudorandom generators, inProceedings of the 29th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1988, 12-24. · Zbl 0717.65001 |

[14] | O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 25-32. |

[15] | S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proof-systems,SIAM Journal on Computing,18:1 (1989), 186-208. · Zbl 0677.68062 |

[16] | J. H?stad, Pseudo-random generators under uniform assumptions, inProceedings of the 22nd ACM Symposium on the Theory of Computing, ACM, New York, 1990, 395-404. |

[17] | J. Hartmanis, N. Immerman, andV. Sewelson, Sparse sets inNP-P: EXPTIME versusNEXPTIME, Information and Control,65 (1985), 158-181. · Zbl 0586.68042 |

[18] | H. Heller, On relativized exponential and probabilistic complexity classes,Information and Computation,71 (1986), 231-243. · Zbl 0628.68047 |

[19] | R. Impagliazzo, L. Levin, and M. Luby, Pseudo-random number generation from one-way functions, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 12-24. |

[20] | R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, inProceedings of the 12th ACM Symposium on the Theory of Computing, ACM, New York, 1980, 302-309. |

[21] | L. Levin, One-way functions and pseudo-random generators,Combinatorica,7 (1987), 357-363. · Zbl 0641.68061 |

[22] | R. Lipton, New directions in testing, inDistributed Computing and Cryptography, volume 2 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, J. Feigenbaum and M. Merritt, eds., American Mathematical Society, Providence, 1991, 191-202. |

[23] | C. Lund, L. Fortnow, H. Karloff, andN. Nisan, Algebraic methods for interactive proof systems,Journal of the ACM,39:4 (1992), 859-868. · Zbl 0799.68097 |

[24] | N. Nisan and A. Wigderson, Hardness vs. randomness, inProceedings of the 29th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1988, 2-11. |

[25] | A. Shamir, IP=PSPACE,Journal of the ACM,39:4 (1992), 869-877. · Zbl 0799.68096 |

[26] | A. Yao, Theory and applications of trapdoor functions, inProceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1982, 80-91. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.