Michael Sipser
ABSTRACT
We study a time bounded variant of Kolmogorov complexity. This notion, together with universal hashing, can be used to show that problems solvable probabilistically in polynomial time are all within the second level of the polynomial time hierarchy. We also discuss applications to the theory of probabilistic constructions.
- 1.L. Adleman, "Two theorems on random polynomial time," 19th FOCS, 1978, 75-83.Google Scholar
- 2.L. Adleman, "Time, space and randomness," MIT/LCS/TM-131, 1979.Google Scholar
- 3.R. Aleliunas, R.M. Karp, R. Lipton, L. Lovasz, and C. Rackoff, "Random walks, universal traversal sequences, and complexity of mazeproblems," 20th FOCS, 218-223, 1979.Google Scholar
- 4.L. Blum, M. Blum, M. Shub, "A simple, secure pseudo-random number generator," CRYPTO 1982.Google Scholar
- 5.C.H. Bennett and J. Gill, "Relative to a random oracle A, pA@@@@NPA@@@@co-NPA with probability one," SKOMP, to appear.Google Scholar
- 6.G.J. Chaitin, "On the length of programs for computing finite binary sequences," JACM 13, 1966, 547-569 and JACM 16, 1969, 145-159. Google ScholarDigital Library
- 7.G.J. Chaitin, "A theory of program size formally identical to information theory," JACM 22, 329-340. Google ScholarDigital Library
- 8.J.L. Carter and M.N. Wegman, "Universal classes of hash function," JCSS 18, no 2, 143-154, 1979.Google ScholarCross Ref
- 9.R.P. Daley, "On the inference of optimal descriptions," TCS 4, 301-319, 1977.Google ScholarCross Ref
- 10.J. Gill, "Complexity of probabilistic Turing machines," SIAM J. of Computing 6, 675-695.Google ScholarDigital Library
- 11.O. Gabber and Z. Galil, "Explicit constructions of linear size super-concentrators," 20th FOCS, 364-370, 1979.Google Scholar
- 12.S. Goldwasser, S. Micali, and P. Tong, "Why and how to establish a private code on a public network," 23rd FOCS, 134-144, 1982.Google Scholar
- 13.M. Furst, J.B. Saxe, M. Sipser, "Parity, circuits, and the polynomial time hierarchy," 22nd FOCS, 260-270, 1981.Google Scholar
- 14.R. Karp, "Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plan," Math. Op. Res. 2, 209-224.Google ScholarDigital Library
- 15.H. Katseff and M. Sipser, "Several results in program size and complexity," 18th FOCS, 1977, 82-89.Google Scholar
- 16.K. Ko "Resource-bounded program-size complexity and pseudo-random sequences," to appear.Google Scholar
- 17.A.N. Kolmogorov, "Three approaches for defining the concept of information quantity," Prob. Inform. Trans. 1, 1-7, 1965.Google Scholar
- 18.L. Levin, "Universal sequential search problems," Prob. Info. Trans. 9, 1973, 265-266.Google Scholar
- 19.A.R. Meyer and E.M. McCreight, "Computationally complex and pseudo-random zero-one valued functions," in Theory of Machines and Computations, Z. Kohavi and A. Paz, eds. Academic Press, 19-42, 1971.Google Scholar
- 20.G. Miller, "Rieman's hypothesis and tests for primality," 7th SIGACT, 1975, 234-239. Google ScholarDigital Library
- 21.G.L. Peterson, "Succinct representations, random strings, and complexity classes," 21st FOCS, 86-95, 1980.Google Scholar
- 22.N. Pippenger, "Superconcentrators," SIAM J. Comput. 6, 298-304, 1972.Google ScholarDigital Library
- 23.N. Pippenger and A. Yao, "Rearrangeable networks with limited depth," SIAM J. Alg. and Disc. Meth. 3, 411-417, 1982.Google ScholarDigital Library
- 24.W. Paul, J. Seiferas, and J. Simon, "An information-theoretic approach to time bounds for on-line-computations," 12th STOC, 357-367, 1980. Google ScholarDigital Library
- 25.M. Rabin, "Probabilistic algorithms in finite fields," MIT/CCS/TR-213. Google ScholarDigital Library
- 26.M. Rabin, "N-process synchronization by 4 log N-valued shared variable," 21st FOCS, 1980, 4-7-410.Google Scholar
- 27.C. Schnorr, "the network complexity and Turing Machine complexity of finite functions," Acts Informa. 7, 1976, 95-107.Google ScholarDigital Library
- 28.A. Shamir, "On the generation of cryptographically strong pseudo-random sequences," 8th ICALP, 545-550, 1981. Google ScholarDigital Library
- 29.M. Sipser, "Borel sets and circuit complexith," 15th STOC, 1983. Google ScholarDigital Library
- 30.M. Sipser, "Three approaches to a definition of finite state randomness," unpublished manuscript.Google Scholar
- 31.R. Solovay and V. Strassen, "A fast Monte-Carol test for primality," SIAM J. on Comput. 6, 1977, 84-85.Google ScholarDigital Library
- 32.L. Stockmeyer, "The polynomial time hierarchy," TCS 3, no.1, 1-22, 1976.Google ScholarCross Ref
Index Terms
- A complexity theoretic approach to randomness
Recommendations
Randomness vs Time
We prove that if BPP EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every sampleable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on ...
Comments