{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T19:10:15Z","timestamp":1734981015972,"version":"3.32.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf01206322","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T14:33:05Z","timestamp":1109255585000},"page":"267-283","source":"Crossref","is-referenced-by-count":7,"title":["Weakly complete problems are not rare"],"prefix":"10.1007","volume":"5","author":[{"given":"David W.","family":"Juedes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, S. A. Terwijn, and Zheng Xizhong, resource bounded randomness and weakly complete problems. InProceedings of the Fifth Annual International Symposium on Algorithms and Computation, Springer-Verlag, 1994, 369?377.","DOI":"10.1007\/3-540-58325-4_201"},{"key":"CR2","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, andJ. Gabarr\u00f3,Structural Complexity I. Springer-Verlag, Berlin, 1988."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett andJ. Gill, Relative to a random oracleA, P A ? NP A ?co-NP A with probability 1.SIAM Journal on Computing 10 (1981), 96?113.","journal-title":"SIAM Journal on Computing"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"L. Berman, On the structure of complete sets: Almost everywhere complexity and infinitely often speedup. InProceedings of the Seventeenth Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1976, 76?80.","DOI":"10.1109\/SFCS.1976.22"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes andJ. H. Lutz, The complexity and distribution of hard problems.SIAM Journal on Computing 24 (1995), 279?295.","journal-title":"SIAM Journal on Computing"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"S. M. Kautz and P. B. Miltersen, Relative to a random oracle, NP is not small.Journal of Computer and System Sciences, to appear. See alsoProceedings of the Ninth Structure in Complexity Theory Conference, IEEE Computer Society Press, 1994, 162?174.","DOI":"10.1109\/SCT.1994.315807"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1145\/174652.174659","volume":"41","author":"A. J. Kfoury","year":"1994","unstructured":"A. J. Kfoury, J. Tiuryn, andP. Urzyczyn, An analysis of ML typability.Journal of the ACM 41 (1994), 368?398.","journal-title":"Journal of the ACM"},{"key":"CR8","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 (1990), 1100?1131.","journal-title":"SIAM Journal on Computing"},{"key":"CR9","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 (1992), 220?258.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, The quantitative structure of exponential time. InProceedings of the Eighth Structure in Complexity Theory Conference, IEEE Computer Society Press, 1993, 158?175.","DOI":"10.1109\/SCT.1993.336530"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, Weakly hard problems.SIAM Journal on Computing, to appear. See alsoProceedings of the Ninth Structure in Complexity Theory Conference, IEEE Computer Society Press, 1994, 146?161.","DOI":"10.1109\/SCT.1994.315808"},{"key":"CR12","unstructured":"J. H. Lutz, Resource-bounded measure. In preparation."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. H. Lutz","year":"1994","unstructured":"J. H. Lutz andE. Mayordomo, Measure, stochasticity, and the density of hard languages.SIAM Journal on Computing 23 (1994), 762?779.","journal-title":"SIAM Journal on Computing"},{"key":"CR14","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 alsoProceedings of the Eleventh Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, 1994, 415?426.","DOI":"10.1007\/3-540-57785-8_159"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"H. G. Mairson, Deciding ML typability is complete for deterministic expontential time. InProceedings of the 17th ACM Symposium on Principles of Programming Languages, ACM Press, January 1990, 382?401.","DOI":"10.1145\/96709.96748"},{"key":"CR16","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":"P. Martin-L\u00f6f, On the definition of random sequences.Information and Control 9 (1966), 602?619.","journal-title":"Information and Control"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"E. Mayordomo, Almost every set in exponential time is P-bi-immune.Theoretical Computer Science 136 (1994), 487?506.","journal-title":"Theoretical Computer Science"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00538763","volume":"16","author":"C. P. Schnorr","year":"1970","unstructured":"C. P. Schnorr, Klassifikation der Zufallsgesetze nach Komplexit\u00e4t und Ordnung.Z. Wahrscheinlichkeitstheorie verw. Geb. 16 (1970), 1?21.","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr, A unified approach to the definition of random sequences.Mathematical Systems Theory 5 (1971), 246?258.","journal-title":"Mathematical Systems Theory"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr, Zuf\u00e4lligkeit und Wahrscheinlichkeit.Lecture Notes in Mathematics 218 (1971).","DOI":"10.1007\/BFb0112458"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr, Process complexity and effective random tests.Journal of Computer and System Sciences 7 (1973), 376?388.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0208013","volume":"8","author":"L. Stockmeyer","year":"1979","unstructured":"L. Stockmeyer andA. K. Chandra, Provably difficult combinatorial games.SIAM Journal on Computing 8 (1979), 151?174.","journal-title":"SIAM Journal on Computing"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2273858","volume":"52","author":"L. J. Stockmeyer","year":"1987","unstructured":"L. J. Stockmeyer, Classifying the computational complexity of problems.Journal of Symbolic Logic 52 (1987), 1?43.","journal-title":"Journal of Symbolic Logic"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206322.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206322\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:40:53Z","timestamp":1734979253000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":23,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01206322"],"URL":"https:\/\/doi.org\/10.1007\/bf01206322","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}