zbMATH — the first resource for mathematics

In search of an easy witness: Exponential time vs. probabilistic polynomial time. (English) Zbl 1059.68047
Summary: Restricting the search space \(\{0,1\}^n\) to the set of truth tables of “easy” Boolean functions on \(\log n\) variables, as well as using some known hardness-randomness tradeoffs, we establish a number of results relating the complexity of exponential-time and probabilistic polynomial-time complexity classes. In particular, we show that NEXP \(\subset\) P/poly \(\Leftrightarrow\) NEXT = MA; this can be interpreted as saying that no derandomization of MA (and, hence, of promise-BBP) is possible unless NEXT contains a hard Boolean function. We also prove several downward closure results for ZPP, RP, BPP, and MA; e.g., we show \(\text{EXP}=\text{BPP} \Leftrightarrow\text{EE}=\text{BPE}\), where EE is the double-exponential time class and BPE is the exponential-time analogue of BPP.

68Q25 Analysis of algorithms and problem complexity
search space
Full Text: DOI
[1] Andreev, A.E.; Clementi, A.E.F.; Rolim, J.D.P., A new general derandomization method, J. assoc. comput. Mach., 45, 1, 179-213, (1998), (preliminary version in ICALP’96) · Zbl 0903.68089
[2] L. Babai, Trading group theory for randomness, in: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 421-429.
[3] Babai, L.; Fortnow, L.; Lund, C., Non-deterministic exponential time has two-prover interactive protocols, Comput. complexity, 1, 3-40, (1991) · Zbl 0774.68041
[4] Babai, L.; Fortnow, L.; Nisan, N.; Wigderson, A., BPP has subexponential time simulations unless EXPTIME has publishable proofs, Complexity, 3, 307-318, (1993) · Zbl 0802.68054
[5] Babai, L.; Moran, S., Arthur – merlin gamesa randomized proof system, and a hierarchy of complexity classes, J. comput. system sci., 36, 254-276, (1988) · Zbl 0652.03029
[6] B. Barak, How to go beyond the black-box simulation barrier, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 106-115.
[7] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in: J. Kilian (Ed.), Advances in Cryptology—CRYPTO’2001, Lecture Notes in Computer Science, Vol. 2139, Springer, Berlin, Germany, 2001, pp. 1-18. · Zbl 1001.68511
[8] H. Buhrman, L. Fortnow, L. Thierauf, Nonrelativizing separations, in: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1988, pp. 8-12. · Zbl 0935.68032
[9] H. Buhrman, S. Homer, Superpolynomial circuits, almost sparse oracles and the exponential hierarchy, in: R. Shyamasundar (Ed.), Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 652, Springer, Berlin, Germany, 1992, pp. 116-127. · Zbl 0925.68183
[10] L. Fortnow, Comparing notions of full derandomization, in: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 28-34.
[11] O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics Series, Vol. 17, Springer, Berlin, 1999. · Zbl 0907.94002
[12] O. Goldreich, D. Zuckerman, Another proof that BPP⊂ PH (and more), Electronic Colloquium on Computational Complexity, TR97-045, 1997.
[13] Hartmanis, J.; Immerman, N.; Sewelson, V., Sparse sets in NP-P: EXPTIME versus NEXPTIME, Inform. control, 65, 158-181, (1985) · Zbl 0586.68042
[14] R. Impagliazzo, M. Naor, Decision trees and downward closures, in: Proceedings of the 3rd Annual IEEE Conference on Structure in Complexity Theory, 1988, pp. 29-38.
[15] R. Impagliazzo, G. Tardos, Decision versus search problems in super-polynomial time, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 222-227.
[16] R. Impagliazzo, A. Wigderson. P=BPP if E requires exponential circuits: derandomizing the XOR Lemma, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 220-229. · Zbl 0962.68058
[17] R. Impagliazzo, A. Wigderson, Randomness vs time: de-randomization under a uniform assumption, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 734-743.
[18] Kabanets, V., Easiness assumptions and hardness tests: trading time for zero error, J. comput. system sci., 63, 2, 236-252, (2001), (preliminary version in CCC’00) · Zbl 0988.68221
[19] Kabanets, V., Derandomizationa brief overview, Bull. eur. assoc. theoret. comput. sci., 76, 88-103, (2002), (also available as ECCC TR02-008) · Zbl 1021.68041
[20] V. Kabanets, C. Rackoff, S. Cook, Efficiently approximable real-valued functions, Electronic Colloquium on Computational Complexity, TR00-034, 2000.
[21] Karp, R.M.; Lipton, R.J., Turing machines that take advice, L’enseignement math., 28, 3-4, 191-209, (1982), (preliminary version in STOC’80) · Zbl 0529.68025
[22] A. Klivans, D. van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 659-667. · Zbl 1345.68174
[23] Lu, C.-J., Derandomizing arthur – merlin games under uniform assumptions, Comput. complexity, 10, 3, 247-259, (2001), (preliminary version in ISAAC’00) · Zbl 0993.68038
[24] P.B. Miltersen, Drandomizing complexity classes, in: S. Rajasekaran, P. Pardalos, J. Reif, J. Rolim (Eds.), Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, Dordrecht, 2001 (a draft is available at www.brics.dk/ bromille).
[25] P.B. Miltersen, N.V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 71-80. · Zbl 1085.68058
[26] Nisan, N.; Wigderson, A., Hardness vs. randomness, J. comput. system sci., 49, 149-167, (1994) · Zbl 0821.68057
[27] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[28] Razborov, A.A.; Rudich, S., Natural proofs, J. comput. system sci., 55, 24-35, (1997) · Zbl 0884.68055
[29] M. Sudan, L. Trevisan, S. Vadhan, Pseudorandom generators without the XOR lemma, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 537-546. · Zbl 1345.68138
[30] A.C. Yao, Theory and applications of trapdoor functions, in: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 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.