{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:10Z","timestamp":1742598610494,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_59","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:18Z","timestamp":1330275558000},"page":"26-37","source":"Crossref","is-referenced-by-count":1,"title":["Completeness and weak completeness under polynomial-size circuits"],"prefix":"10.1007","author":[{"given":"David W.","family":"Juedes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E. Allender","year":"1988","unstructured":"E. Allender and R. Rubinstein. P-printable sets. SIAM Journal on Computing, 17:1193\u20131202, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0022-0000(89)90021-4","volume":"39","author":"E. W. Allender","year":"1989","unstructured":"E. W. Allender. Some consequences of the existence of pseudorandom generators. Journal of Computer and System Sciences, 39:101\u2013124, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0890-5401(90)90052-J","volume":"86","author":"E. W. Allender","year":"1990","unstructured":"E. W. Allender and O. Watanabe. Kolmogorov complexity and degrees of tally sets. Information and Computation, 86:160\u2013178, 1990.","journal-title":"Information and Computation"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, S. A. Terwijn, and Zheng Xizhong. Resource bounded randomness and weakly complete problems. In Proceedings of the Fifth Annual International Symposium on Algorithms and Computation, pages 369\u2013377. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-58325-4_201"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/BF00264313","volume":"23","author":"J. L. Balc\u00e1zar","year":"1986","unstructured":"J. L. Balc\u00e1zar and R. V. Book. Sets with small generalized Kolmogorov complexity. Acta Informatica, 23:679\u2013688, 1986.","journal-title":"Acta Informatica"},{"key":"3_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, Berlin, 1988."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. L. Balc\u00e1zar","year":"1985","unstructured":"J. L. Balc\u00e1zar and U. Sch\u00f6ning. Bi-immune sets for complexity classes. Mathematical Systems Theory, 18:1\u201310, 1985.","journal-title":"Mathematical Systems Theory"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1145\/28869.28880","volume":"34","author":"R. Book","year":"1987","unstructured":"R. Book and D.-Z. Du. The existence and density of generalized complexity cores. Journal of the ACM, 34:718\u2013730, 1987.","journal-title":"Journal of the ACM"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"R. Book, D.-Z Du, and D. Russo. On polynomial and generalized complexity cores. In Proceedings of the Third Structure in Complexity Theory Conference, pages 236\u2013250, 1988.","DOI":"10.1109\/SCT.1988.5283"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G. J. Chaitin","year":"1966","unstructured":"G. J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association for Computing Machinery, 13:547\u2013569, 1966.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR11","volume-title":"Ph.D. thesis","author":"D.-Z. Du","year":"1985","unstructured":"D.-Z. Du. Generalized complexity cores and levelability of intractable sets. Ph.D. thesis, University of California, Santa Barbara, 1985."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(89)90015-7","volume":"63","author":"D.-Z. Du","year":"1989","unstructured":"D.-Z. Du and R. Book. On inefficient special cases of NP-complete problems. Theoretical Computer Science, 63:239\u2013252, 1989.","journal-title":"Theoretical Computer Science"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/2455.214111","volume":"35","author":"S. Even","year":"1985","unstructured":"S. Even, A. Selman, and Y. Yacobi. Hard core theorems for complexity classes. Journal of the ACM, 35:205\u2013217, 1985.","journal-title":"Journal of the ACM"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on the Foundations of Computer Science, pages 439\u2013445, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities. Theoretical Computer Science, 34:17\u201332, 1984.","journal-title":"Theoretical Computer Science"},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/3-540-16486-3_97","volume-title":"Structure in Complexity Theory","author":"D. T. Huynh","year":"1986","unstructured":"D. T. Huynh. Resource-bounded Kolmogorov complexity of hard languages, Structure in Complexity Theory, pages 184\u2013195. Springer-Verlag, Berlin, 1986."},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(87)90181-5","volume":"24","author":"D. T. Huynh","year":"1987","unstructured":"D. T. Huynh. On solving hard problems by polynomial-size circuits. Information Processing Letters, 24:171\u2013176, 1987.","journal-title":"Information Processing Letters"},{"key":"3_CR18","unstructured":"D. W. Juedes. The Complexity and Distribution of Computationally Useful Problems. Ph.D. thesis, Iowa State University, 1994."},{"key":"3_CR19","unstructured":"D. W. Juedes. Weakly complete problems are not rare. submitted, 1994."},{"issue":"2","key":"3_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"David W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24, 1995. to appear.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"D. W. Juedes and J. H. Lutz. Weak completeness in E and E2. Theoretical Computer Science, 1995. to appear.","DOI":"10.1016\/0304-3975(95)80030-D"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40\u201356, 1982.","journal-title":"Information and Control"},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013104. Plenum Press, New York, 1972."},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"3_CR25","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0304-3975(86)90081-2","volume":"48","author":"K. Ko","year":"1986","unstructured":"K. Ko. On the notion of infinite pseudorandom sequences. Theoretical Computer Science, 48:9\u201333, 1986.","journal-title":"Theoretical Computer Science"},{"key":"3_CR26","first-page":"1","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov. Three approaches to the quantitative definition of \u2018information'. Problems of Information Transmission, 1:1\u20137, 1965.","journal-title":"Problems of Information Transmission"},{"key":"3_CR27","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"L. A. Levin","year":"1984","unstructured":"L. A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61:15\u201337, 1984.","journal-title":"Information and Control"},{"key":"3_CR28","unstructured":"L. Longpr\u00e9. Resource Bounded Kolmogorov Complexity, a Link Between Computational Complexity and Information Theory. Ph.D. thesis, Cornell University, 1986. Technical Report TR-86-776."},{"key":"3_CR29","unstructured":"J. H. Lutz. Resource-bounded measure. in preparation."},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, to appear. See also Proceedings of the Ninth Structure in Complexity Theory Conference, 1994, pp. 146\u2013161. IEEE Computer Society Press.","DOI":"10.1109\/SCT.1994.315808"},{"key":"3_CR31","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J. H. Lutz","year":"1990","unstructured":"J. H. Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19:1100\u20131131, 1990.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR32","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, to appear. See also Proceedings of the Eleventh Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1994, pp. 415\u2013426.","DOI":"10.1007\/3-540-57785-8_159"},{"key":"3_CR34","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. H. Lutz","year":"1994","unstructured":"J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23:762\u2013779, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR35","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321892.321895","volume":"22","author":"N. Lynch","year":"1975","unstructured":"N. Lynch. On reducibility to complex or sparse sets. Journal of the ACM, 22:341\u2013345, 1975.","journal-title":"Journal of the ACM"},{"key":"3_CR36","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"P. Martin-L\u00f6f. Complexity oscillations in infinite binary sequences. Zeitschrift f\u00fcr Wahrscheinlichkeitstheory und Verwandte Gebiete, 19:225\u2013230, 1971.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheory und Verwandte Gebiete"},{"key":"3_CR37","unstructured":"E. Mayordomo. Contributions to the study of resource-bounded measure. Ph.D. thesis, Universitat Polit\u00e8cnica de Catalunya, 1994."},{"key":"3_CR38","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0304-3975(86)90140-4","volume":"70","author":"P. Orponen","year":"1986","unstructured":"P. Orponen. A classification of complexity core lattices. Theoretical Computer Science, 70:121\u2013130, 1986.","journal-title":"Theoretical Computer Science"},{"key":"3_CR39","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(86)80024-9","volume":"70","author":"P. Orponen","year":"1986","unstructured":"P. Orponen and U. Sch\u00f6ning. The density and complexity of polynomial cores for intractable sets. Information and Control, 70:54\u201368, 1986.","journal-title":"Information and Control"},{"key":"3_CR40","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01692061","volume":"20","author":"D. A. Russo","year":"1987","unstructured":"D. A. Russo and P. Orponen. On P-subset structures. Mathematical Systems Theory, 20:129\u2013136, 1987.","journal-title":"Mathematical Systems Theory"},{"key":"3_CR41","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity-theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"3_CR42","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"S. Skyum and L. G. Valiant. A complexity theory based on boolean algebra. Journal of the ACM, 32:484\u2013502, 1985.","journal-title":"Journal of the ACM"},{"key":"3_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. J. Solomonoff","year":"1964","unstructured":"R. J. Solomonoff. A formal theory of inductive inference. Information and Control, 7:1\u201322, 224\u2013254, 1964.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:42:00Z","timestamp":1742596920000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}