More Web Proxy on the site http://driver.im/

Article

Free access

A complexity theoretic approach to randomness

Author:

Michael SipserAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 330 - 335

https://doi.org/10.1145/800061.808762

Published: 01 December 1983 Publication History

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]

G.J. Chaitin, "On the length of programs for computing finite binary sequences," JACM 13, 1966, 547-569 and JACM 16, 1969, 145-159.

Digital Library

[7]

G.J. Chaitin, "A theory of program size formally identical to information theory," JACM 22, 329-340.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

G. Miller, "Rieman's hypothesis and tests for primality," 7th SIGACT, 1975, 234-239.

Digital Library

[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.

Digital Library

[23]

N. Pippenger and A. Yao, "Rearrangeable networks with limited depth," SIAM J. Alg. and Disc. Meth. 3, 411-417, 1982.

Digital 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.

Digital Library

[25]

M. Rabin, "Probabilistic algorithms in finite fields," MIT/CCS/TR-213.

Digital Library

[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.

Digital Library

[28]

A. Shamir, "On the generation of cryptographically strong pseudo-random sequences," 8th ICALP, 545-550, 1981.

Digital Library

[29]

M. Sipser, "Borel sets and circuit complexith," 15th STOC, 1983.

Digital Library

[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.

Digital Library

[32]

L. Stockmeyer, "The polynomial time hierarchy," TCS 3, no.1, 1-22, 1976.

Cited By

Semenov AShen AVereshchagin N(2024)Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)Theory of Probability & Its Applications10.1137/S0040585X97T99164768:4(582-606)Online publication date: 7-Feb-2024
https://doi.org/10.1137/S0040585X97T991647
Li JPyne ETell R(2024)Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00095(1-13)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00095
Hromkovič J(2024)Kolmogorov Complexity and Nondeterminism Versus Determinism for Polynomial Time ComputationsTheoretical Computer Science10.1016/j.tcs.2024.114747(114747)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114747
Show More Cited By

Index Terms

A complexity theoretic approach to randomness
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Probabilistic computation

Recommendations

Randomness and Completeness in Computational Complexity
Randomness and completeness in computational complexity
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

Copyright © 1983 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

262
Total Citations
View Citations
873
Total Downloads

Downloads (Last 12 months)374
Downloads (Last 6 weeks)47

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Semenov AShen AVereshchagin N(2024)Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)Theory of Probability & Its Applications10.1137/S0040585X97T99164768:4(582-606)Online publication date: 7-Feb-2024
https://doi.org/10.1137/S0040585X97T991647
Li JPyne ETell R(2024)Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00095(1-13)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00095
Hromkovič J(2024)Kolmogorov Complexity and Nondeterminism Versus Determinism for Polynomial Time ComputationsTheoretical Computer Science10.1016/j.tcs.2024.114747(114747)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114747
Liu YPass R(2024)On One-Way Functions, the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity, and Computational DepthTheory of Cryptography10.1007/978-3-031-78011-0_8(222-252)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_8
Brandt N(2024)Lower Bounds for Levin–Kolmogorov ComplexityTheory of Cryptography10.1007/978-3-031-78011-0_7(191-221)Online publication date: 2-Dec-2024
https://doi.org/10.1007/978-3-031-78011-0_7
Chaidos PKiayias AReyzin LZinovyev A(2024)Approximate Lower Bound ArgumentsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_3(55-84)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_3
Liu YPass R(2024)A Direct PRF Construction from Kolmogorov ComplexityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_14(375-406)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_14
Hirahara SLu ZRen H(2023)Bounded RelativizationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.6(1-45)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.6
Верещагин НVereshchagin NСемeнов АSemenov AШень АShen' A(2023)Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика)Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)Теория вероятностей и ее примененияTeoriya Veroyatnostei i ee Primeneniya10.4213/tvp565068:4(719-750)Online publication date: 23-Oct-2023
https://doi.org/10.4213/tvp5650
Soos MAggarwal DChakraborty SMeel KObremski MElkind E(2023)Engineering an efficient approximate DNF-counterProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/226(2031-2038)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/226
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents