Abstract
This paper explores further the relationship between randomness and complexity. The concept of time-/space-bounded Kolmogorov complexity of languages is introduced. Among others we show that there exists a language L in DTIME(22lin) such that the 2poly-time-bounded Kolmogorov complexity of L is exponential almost everywhere. We study time-/space- bounded Kolmogorov complexity of languages that are DTIME(22lin)-(SPACE (2lin)-) hard under polynomial-time Turing reductions. The connection between Kolmogorov-random languages and almost everywhere hard languages is investigated. We also show that Kolmogorov randomness implies Church randomness. Finally, we work out the relationship between time-/space- bounded Kolmogorov complexity and time-/space- bounded descriptional complexity of Boolean circuits and formulas for hard languages. This result provides a classification of exponential-size circuits and formulas in terms of the amount of information contained in them.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.: "Two Theorems on Random Polynomial Time", Proc. 19th FOCS, pp. 75–83, 1978.
Balcázar, J.L. & Schöning, U.: "Bi-immune Sets for Complexity Classes", to appear in Math. Syst. Theor.
Berman, L.: "On the Structure of Complete Sets: Almost Everywhere Complexity And Infinitely Often Speedup", Proc. 17th FOCS, pp. 76–80, 1976.
Berman, L. & Hartmanis, J.: "On Isomorphisms and Density of NP and Other Complete Sets", SIAM J. Comput. 6, pp. 305–322, 1977.
Chaitin, G.J.: "On the Length of Programs for Computing Finite Binary Sequences", J.ACM 13, pp. 547–569, 1966.
Church, A.: "On the Concept of Random Sequence", Bull. AMS 46, pp. 130–135, 1940.
Cook, S.A.: "The Classification of Problems Which Have Fast Parallel Algorithms", Proc. FCT'83, LNCS 158, pp. 78–93, 1983.
Di Paola, R.A.: "Random Sets in Subrecursive Hierarchies", J. ACM 16, pp. 621–630, 1969.
Garey, M.R. & Johnson, D.S.: "Computers and Intractability", Freeman & Co., 1979.
Hartmanis, J.: "Generalized Kolmogorov Complexity and the Structure of Feasible Computations", Proc. 24th FOCS, pp. 439–445, 1983.
Hopcroft, J.E. & Ullman, J.D.: "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, 1979.
Huynh, D.T.: "Some Observations about the Randomness of Hard Problems", Manuscript, 1985.
Kannan, R.: "Circuit-Size Lower Bounds and Non-reducibility to Sparse Sets", Infor. & Contr. 55, pp. 40–56, 1982.
Karp, R.M. & Lipton, R.J.: "Some Connections between Nonuniform and Uniform Complexity Classes", Proc. 12th STOC, pp. 302–309, 1980.
Ko, K.: "Resource-Bounded Program-Size Complexity and Pseudo-Random Sequences", to appear.
Kolmogorov, A.N.: "Three Approaches for Defining the Concept of Information Quantity", Probl. Inform. Trans. 1, pp. 1–7, 1965.
Ladner, R.E.: "The Circuit Value Problem Is Log-space Complete for P", SIGACT News 7, pp. 18–20, 1975.
Loveland, D.W.: "A Variant of the Kolmogorov Concept of Complexity", Infor. & Contr. 15, pp. 510–526, 1969.
Lynch, N.: ‘Log Space Recognition and Translation of Parenthesis Languages", J. ACM 24, pp. 583–590, 1977.
Martin-Löf, P.: "On the Definition of Random Sequences", Infor. & Contr. 9, pp. 602–619, 1966.
Martin-Löf, P.: "Complexity Oscillations in Infinite Binary Sequences", Z. Wahrsch.-theor. verw. Geb. 19, pp. 225–230, 1971.
Mehlhorn, K.: "Bracket Languages Are Recognizable in Logarithmic Space", TR Univ. Saarlandes, Saarbrücken, 1975.
Meyer, A.R. & McCreight, E.M.: "Computationally Complex and Pseudo-random Zero-one Valued Functions", in "Theory of Machines and Computations", Kohavi and Paz, eds., Academic Press, pp. 19–42, 1971.
Paul, W., Seiferas, J. & Simon, J.: "An Information-theoretic Approach to Time Bounds for On-line Computation", Proc. 12th STOC. pp. 357–367, 1980.
Rogers, H.: "Theory of Recursive Functions and Effective Computability", McGraw-Hill, 1967.
Ruzzo, W.L.: "On Uniform Circuit Complexity", J. Comput. Syst. Sci. 22, pp. 365–383, 1981.
Savage, J.E.: "The Complexity of Computing", Wiley & Sons, New York, 1976.
Schnorr, C.P.: "Zulfalligkeit und Wahrscheinlichkeit", LNM 218, Springer Verlag, 1971.
Sipser, M.: "A Complexity Theoretic Approach to Randomness", Proc. 15th STOC, pp. 330–335, 1983.
Stockmeyer, L.J.: "The Complexity of Decision Problems in Automata Theory and Logic", MAC TR-133, MIT, 1974.
Valiant, L.G.: "Completeness Classes in Algebra", Proc. 11th STOC, pp. 249–261, 1979.
Wilber, R.E.: "Randomness and the Density of Hard Problems", Proc. 24th FOCS, pp. 335–342, 1983.
Wilson, C.B.: "Relativized Circuit Complexity", Proc. 24th FOCS, pp. 329–334, 1983.
Yao, A.C.: "Theory and Applications of Trapdoor Functions", Proc. 23rd FOCS, pp. 80–91, 1982.
Zvonkin, A.K. & Levin, L.A.: The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms", Russian Math. Survey 25, pp. 83–124, 1970.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huynh, D.T. (1986). Resource-bounded Kolmogorov complexity of hard languages. In: Selman, A.L. (eds) Structure in Complexity Theory. Lecture Notes in Computer Science, vol 223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16486-3_97
Download citation
DOI: https://doi.org/10.1007/3-540-16486-3_97
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16486-9
Online ISBN: 978-3-540-39825-7
eBook Packages: Springer Book Archive