A complexity theoretic approach to randomness

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.

REFERENCES

• 1: L. Adleman, "Two theorems on random polynomial time," 19th FOCS, 1978, 75-83.
• 2: L. Adleman, "Time, space and randomness," MIT/LCS/TM-131, 1979.
• 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.
• 4: L. Blum, M. Blum, M. Shub, "A simple, secure pseudo-random number generator," CRYPTO 1982.
• 5: C.H. Bennett and J. Gill, "Relative to a random oracle A, pA@@@@NPA@@@@co-NPA with probability one," SKOMP, to appear.
• 6: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
• 7: Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM (JACM), v.22 n.3, p.329-340, July 1975 [doi>10.1145/321892.321894]
• 8: J.L. Carter and M.N. Wegman, "Universal classes of hash function," JCSS 18, no 2, 143-154, 1979.
• 9: R.P. Daley, "On the inference of optimal descriptions," TCS 4, 301-319, 1977.
• 10: J. Gill, "Complexity of probabilistic Turing machines," SIAM J. of Computing 6, 675-695.
• 11: O. Gabber and Z. Galil, "Explicit constructions of linear size super-concentrators," 20th FOCS, 364-370, 1979.
• 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.
• 13: M. Furst, J.B. Saxe, M. Sipser, "Parity, circuits, and the polynomial time hierarchy," 22nd FOCS, 260-270, 1981.
• 14: R. Karp, "Probabilistic analysis of partitioning algorithms for the travelling-salesman problem in the plan," Math. Op. Res. 2, 209-224.
• 15: H. Katseff and M. Sipser, "Several results in program size and complexity," 18th FOCS, 1977, 82-89.
• 16: K. Ko "Resource-bounded program-size complexity and pseudo-random sequences," to appear.
• 17: A.N. Kolmogorov, "Three approaches for defining the concept of information quantity," Prob. Inform. Trans. 1, 1-7, 1965.
• 18: L. Levin, "Universal sequential search problems," Prob. Info. Trans. 9, 1973, 265-266.
• 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.
• 20: Gary L. Miller, Riemann's Hypothesis and tests for primality, Proceedings of seventh annual ACM symposium on Theory of computing, p.234-239, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803773]
• 21: G.L. Peterson, "Succinct representations, random strings, and complexity classes," 21st FOCS, 86-95, 1980.
• 22: N. Pippenger, "Superconcentrators," SIAM J. Comput. 6, 298-304, 1972.
• 23: N. Pippenger and A. Yao, "Rearrangeable networks with limited depth," SIAM J. Alg. and Disc. Meth. 3, 411-417, 1982.
• 24: Wolfgang J. Paul , Joel I. Seiferas , Janos Simon, An information-theoretic approach to time bounds for on-line computation (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.357-367, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804685]
• 25: M. O. Rabin, PROBABILISTIC ALGORITHM IN FINITE FIELDS, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 26: M. Rabin, "N-process synchronization by 4 log N-valued shared variable," 21st FOCS, 1980, 4-7-410.
• 27: C. Schnorr, "the network complexity and Turing Machine complexity of finite functions," Acts Informa. 7, 1976, 95-107.
• 28: Adi Shamir, On the Generation of Cryptographically Strong Pseudo-Random Sequences, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.544-550, July 13-17, 1981
• 29: Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
• 30: M. Sipser, "Three approaches to a definition of finite state randomness," unpublished manuscript.
• 31: R. Solovay and V. Strassen, "A fast Monte-Carol test for primality," SIAM J. on Comput. 6, 1977, 84-85.
• 32: L. Stockmeyer, "The polynomial time hierarchy," TCS 3, no.1, 1-22, 1976.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Algorithms