{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:50:12Z","timestamp":1787496612388,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_97","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:45:35Z","timestamp":1330177535000},"page":"184-195","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Resource-bounded Kolmogorov complexity of hard languages"],"prefix":"10.1007","author":[{"given":"Dung T.","family":"Huynh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L.: \"Two Theorems on Random Polynomial Time\", Proc. 19th FOCS, pp. 75\u201383, 1978.","DOI":"10.1109\/SFCS.1978.37"},{"key":"13_CR2","unstructured":"Balc\u00e1zar, J.L. & Sch\u00f6ning, U.: \"Bi-immune Sets for Complexity Classes\", to appear in Math. Syst. Theor."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Berman, L.: \"On the Structure of Complete Sets: Almost Everywhere Complexity And Infinitely Often Speedup\", Proc. 17th FOCS, pp. 76\u201380, 1976.","DOI":"10.1109\/SFCS.1976.22"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L. & Hartmanis, J.: \"On Isomorphisms and Density of NP and Other Complete Sets\", SIAM J. Comput. 6, pp. 305\u2013322, 1977.","journal-title":"SIAM J. Comput."},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G.J. Chaitin","year":"1966","unstructured":"Chaitin, G.J.: \"On the Length of Programs for Computing Finite Binary Sequences\", J.ACM 13, pp. 547\u2013569, 1966.","journal-title":"J.ACM"},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1090\/S0002-9904-1940-07154-X","volume":"46","author":"A. Church","year":"1940","unstructured":"Church, A.: \"On the Concept of Random Sequence\", Bull. AMS 46, pp. 130\u2013135, 1940.","journal-title":"Bull. AMS"},{"key":"13_CR7","first-page":"78","volume":"158","author":"S.A. Cook","year":"1983","unstructured":"Cook, S.A.: \"The Classification of Problems Which Have Fast Parallel Algorithms\", Proc. FCT'83, LNCS 158, pp. 78\u201393, 1983.","journal-title":"Proc. FCT'83, LNCS"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1145\/321541.321551","volume":"16","author":"R.A. Paola Di","year":"1969","unstructured":"Di Paola, R.A.: \"Random Sets in Subrecursive Hierarchies\", J. ACM 16, pp. 621\u2013630, 1969.","journal-title":"J. ACM"},{"key":"13_CR9","unstructured":"Garey, M.R. & Johnson, D.S.: \"Computers and Intractability\", Freeman & Co., 1979."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: \"Generalized Kolmogorov Complexity and the Structure of Feasible Computations\", Proc. 24th FOCS, pp. 439\u2013445, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"13_CR11","unstructured":"Hopcroft, J.E. & Ullman, J.D.: \"Introduction to Automata Theory, Languages, and Computation\", Addison-Wesley, 1979."},{"key":"13_CR12","unstructured":"Huynh, D.T.: \"Some Observations about the Randomness of Hard Problems\", Manuscript, 1985."},{"key":"13_CR13","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R.: \"Circuit-Size Lower Bounds and Non-reducibility to Sparse Sets\", Infor. & Contr. 55, pp. 40\u201356, 1982.","journal-title":"Infor. & Contr."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M. & Lipton, R.J.: \"Some Connections between Nonuniform and Uniform Complexity Classes\", Proc. 12th STOC, pp. 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"13_CR15","unstructured":"Ko, K.: \"Resource-Bounded Program-Size Complexity and Pseudo-Random Sequences\", to appear."},{"key":"13_CR16","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: \"Three Approaches for Defining the Concept of Information Quantity\", Probl. Inform. Trans. 1, pp. 1\u20137, 1965.","journal-title":"Probl. Inform. Trans."},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: \"The Circuit Value Problem Is Log-space Complete for P\", SIGACT News 7, pp. 18\u201320, 1975.","journal-title":"SIGACT News"},{"key":"13_CR18","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1016\/S0019-9958(69)90538-5","volume":"15","author":"D.W. Loveland","year":"1969","unstructured":"Loveland, D.W.: \"A Variant of the Kolmogorov Concept of Complexity\", Infor. & Contr. 15, pp. 510\u2013526, 1969.","journal-title":"Infor. & Contr."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N. Lynch","year":"1977","unstructured":"Lynch, N.: \u2018Log Space Recognition and Translation of Parenthesis Languages\", J. ACM 24, pp. 583\u2013590, 1977.","journal-title":"J. ACM"},{"key":"13_CR20","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: \"On the Definition of Random Sequences\", Infor. & Contr. 9, pp. 602\u2013619, 1966.","journal-title":"Infor. & Contr."},{"key":"13_CR21","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"Martin-L\u00f6f, P.: \"Complexity Oscillations in Infinite Binary Sequences\", Z. Wahrsch.-theor. verw. Geb. 19, pp. 225\u2013230, 1971.","journal-title":"Z. Wahrsch.-theor. verw. Geb."},{"key":"13_CR22","volume-title":"Bracket Languages Are Recognizable in Logarithmic Space","author":"K. Mehlhorn","year":"1975","unstructured":"Mehlhorn, K.: \"Bracket Languages Are Recognizable in Logarithmic Space\", TR Univ. Saarlandes, Saarbr\u00fccken, 1975."},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"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\u201342, 1971.","DOI":"10.1016\/B978-0-12-417750-5.50006-3"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Paul, W., Seiferas, J. & Simon, J.: \"An Information-theoretic Approach to Time Bounds for On-line Computation\", Proc. 12th STOC. pp. 357\u2013367, 1980.","DOI":"10.1145\/800141.804685"},{"key":"13_CR25","unstructured":"Rogers, H.: \"Theory of Recursive Functions and Effective Computability\", McGraw-Hill, 1967."},{"key":"13_CR26","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L. Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: \"On Uniform Circuit Complexity\", J. Comput. Syst. Sci. 22, pp. 365\u2013383, 1981.","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR27","volume-title":"The Complexity of Computing","author":"J.E. Savage","year":"1976","unstructured":"Savage, J.E.: \"The Complexity of Computing\", Wiley & Sons, New York, 1976."},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P.: \"Zulfalligkeit und Wahrscheinlichkeit\", LNM 218, Springer Verlag, 1971.","DOI":"10.1007\/BFb0112458"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Sipser, M.: \"A Complexity Theoretic Approach to Randomness\", Proc. 15th STOC, pp. 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"13_CR30","unstructured":"Stockmeyer, L.J.: \"The Complexity of Decision Problems in Automata Theory and Logic\", MAC TR-133, MIT, 1974."},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: \"Completeness Classes in Algebra\", Proc. 11th STOC, pp. 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Wilber, R.E.: \"Randomness and the Density of Hard Problems\", Proc. 24th FOCS, pp. 335\u2013342, 1983.","DOI":"10.1109\/SFCS.1983.49"},{"key":"13_CR33","doi-asserted-by":"crossref","unstructured":"Wilson, C.B.: \"Relativized Circuit Complexity\", Proc. 24th FOCS, pp. 329\u2013334, 1983.","DOI":"10.1109\/SFCS.1983.66"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: \"Theory and Applications of Trapdoor Functions\", Proc. 23rd FOCS, pp. 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"},{"key":"13_CR35","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"A.K. Zvonkin","year":"1970","unstructured":"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\u2013124, 1970.","journal-title":"Russian Math. Survey"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_97","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:18:57Z","timestamp":1578518337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_97"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_97","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}