{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:50Z","timestamp":1742617190502,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995]]},"DOI":"10.1007\/3-540-60249-6_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:57:26Z","timestamp":1330279046000},"page":"156-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Effective category and measure in abstract complexity theory"],"prefix":"10.1007","author":[{"given":"Cristian","family":"Calude","sequence":"first","affiliation":[]},{"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and M. Strauss. Measure on small complexity classes, with applications for BPP, FOCS'94, 1994, 807\u2013818.","DOI":"10.1109\/SFCS.1994.365713"},{"issue":"2","key":"11_CR2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"M. Blum. A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14(2) (1967), 322\u2013336.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"11_CR3","first-page":"257","volume":"18","author":"M. Blum","year":"1967","unstructured":"M. Blum. On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18(2) (1967), 257\u2013265.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"11_CR4","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1145\/321679.321691","volume":"19","author":"A. Borodin","year":"1972","unstructured":"A. Borodin. Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19(1) (1972), 158\u2013174.","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR5","volume-title":"Computability\u2014A Mathematical Sketchbook","author":"D. S. Bridges","year":"1994","unstructured":"D. S. Bridges. Computability\u2014A Mathematical Sketchbook, Springer-Verlag, Berlin, 1994."},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/0304-3975(94)00050-6","volume":"132","author":"D. S. Bridges","year":"1994","unstructured":"D. S. Bridges and C. Calude. On recursive bounds for the exceptional values in speed-up, Theoret. Comput. Sci. 132 (1994), 387\u2013394.","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1002\/malq.19820282707","volume":"28","author":"C. Calude","year":"1982","unstructured":"C. Calude. Topological size of sets of partial recursive functions, Z. Math. Logik Grundlag. Math. 28(1982), 455\u2013462.","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"11_CR8","volume-title":"Theories of Computational Complexity","author":"C. Calude","year":"1988","unstructured":"C. Calude. Theories of Computational Complexity, North-Holland, Amsterdam, New York, Oxford, Tokyo, 1988."},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0304-3975(91)90331-U","volume":"87","author":"C. Calude","year":"1991","unstructured":"C. Calude. Relativized topological size of sets of partial recursive functions, Theoret. Comput. Sci. 87 (1991), 347\u2013352.","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1002\/malq.19920380112","volume":"3","author":"C. Calude","year":"1992","unstructured":"C. Calude, G. Istrate, and M. Zimand. Recursive Baire classification and speedable functions, Z. Math. Logik Grundlang. Math. 3 (1992), 169\u2013178.","journal-title":"Z. Math. Logik Grundlang. Math."},{"key":"11_CR11","first-page":"63","volume":"66","author":"C. Calude","year":"1994","unstructured":"C. Calude, H. J\u00fcrgensen, and M. Zimand. Is independence an exception?, Applied Math. Comput. 66 (1994), 63\u201376.","journal-title":"Applied Math. Comput."},{"key":"11_CR12","unstructured":"C. Calude and M. Zimand. On three theorems in abstract complexity theory: A topological glimpse, Abstracts of the Second International Colloquium on Semigroups, Formal Languages and Combinatorics on Words, Kyoto, Japan, 1992, 11\u201312."},{"issue":"1","key":"11_CR13","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1145\/321679.321692","volume":"19","author":"R. L. Constable","year":"1972","unstructured":"R. L. Constable. The operator gap, J. Assoc. Comput. Mach. 19(1) (1972), 175\u2013183.","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR14","unstructured":"S. Fenner. Notions of resource-bounded category and genericity, Proc. 6th Structure in Complexity Theory, 1991, 347\u2013352."},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01084088","volume":"6","author":"R. Freidzon","year":"1976","unstructured":"R. Freidzon. Families of recursive predicates of measure zero, J. Soviet Math. 6 (1976), 449\u2013455.","journal-title":"J. Soviet Math."},{"key":"11_CR16","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/0022-0000(90)90006-7","volume":"40","author":"M. A. Fulk","year":"1990","unstructured":"M. A. Fulk. A note on a.e. h-complex functions, J. Comput. System Sciences 40 (1990), 444\u2013449.","journal-title":"J. Comput. System Sciences"},{"issue":"3","key":"11_CR17","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/321650.321661","volume":"18","author":"J. Hartmanis","year":"1971","unstructured":"J. Hartmanis and J. E. Hopcroft. An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18(3) (1971), 444\u2013475.","journal-title":"J. Assoc. Comput. Mach."},{"key":"11_CR18","doi-asserted-by":"crossref","first-page":"21","DOI":"10.2307\/2271512","volume":"36","author":"J. Helm","year":"1971","unstructured":"J. Helm and P. Young. On size vs. efficiency for programs admitting speed-ups, J. Symbolic Logic 36 (1971), 21\u201327.","journal-title":"J. Symbolic Logic"},{"issue":"6","key":"11_CR19","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J. Lutz","year":"1990","unstructured":"J. Lutz. Category and measure in complexity theory, SIAM Journal Computing 19(6) (1990), 1100\u20131131.","journal-title":"SIAM Journal Computing"},{"key":"11_CR20","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. Lutz","year":"1992","unstructured":"J. Lutz. Almost everywhere high nonuniform complexity, J. Comput. System Sciences 44 (1992), 220\u2013258.","journal-title":"J. Comput. System Sciences"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"J. Lutz. The quantitative structure of exponential time, Proceedings of the 8th Structure in Complexity Theory Conference, 1993, 158\u2013175.","DOI":"10.1109\/SCT.1993.336530"},{"key":"11_CR22","volume-title":"An Introduction to Automata Theory, Languages and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. An Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979."},{"key":"11_CR23","volume-title":"An Introduction to the General Theory of Algorithms","author":"M. Machtey","year":"1978","unstructured":"M. Machtey and P. Young. An Introduction to the General Theory of Algorithms, North-Holland, Amsterdam, 1978."},{"key":"11_CR24","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, Theoret. Comput. Sci., 136(1994), 487\u2013506.","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. On the size of sets of computable functions, Annual IEEE Symp. on Switching and Automata Theory, Univ. Iowa, 1973, 190\u2013196.","DOI":"10.1109\/SWAT.1973.23"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"K. Melhorn. The almost all theory of subrecursive degrees is decidable, Proc. Second ICALP, Lecture Notes in Computer Science, Springer-Verlag, 1974, 1317\u2013325.","DOI":"10.1007\/978-3-662-21545-6_23"},{"issue":"1","key":"11_CR27","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2272545","volume":"37","author":"A. R. Meyer","year":"1972","unstructured":"A. R. Meyer and P. C. Fischer. Computational speed-up by effective operators, J. Symbolic Logic 37(1) (1972), 55\u201368.","journal-title":"J. Symbolic Logic"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"E. McCreight and A. Meyer. Classes of computable functions defined by bounds on computation: preliminary report, Conf. Rec. ACM Symp. on Theory of Computing, 1965, 79\u201388.","DOI":"10.1145\/800169.805423"},{"key":"11_CR29","unstructured":"A. R. Meyer and K. Winklman. The fundamental theorem of complexity theory, in J. W. de Bakker and J. van Leeuwen (eds.). Found. Comput. Sci. III Part 1: Automata, Data Structures, Complexity, Mathematical Centre Tracts, vol. 108, Amsterdam, 1979, 97\u2013112."},{"key":"11_CR30","volume-title":"Technical Report 2","author":"M. Rabin","year":"1960","unstructured":"M. Rabin. Degree of Difficulty of Computing a Function, Hebrew University, Jerusalem, Technical Report 2 (April 25), 1960."},{"key":"11_CR31","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"H. Rogers. Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967."},{"key":"11_CR32","unstructured":"C. P. Schnorr. Does the computational speed-up concern programming?, Proc. First Internat. Conf. on Automata, Languages and Programming, 1972, 589\u2013596."},{"key":"11_CR33","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, J. Comput. System Sciences 7 (1973), 376\u2013388.","journal-title":"J. Comput. System Sciences"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"J. Seiferas. Machine-independent complexity theory, in J. van Leeuwen (ed.). Handbook of Theoretical Computer Science, vol. A, Elsevier, 1990, 165\u2013186.","DOI":"10.1016\/B978-0-444-88071-0.50008-4"},{"key":"11_CR35","unstructured":"J. Seiferas and A. R. Meyer. Characterization of realizable space complexities, Annals of Pure and Applied Logic (to appear)."},{"key":"11_CR36","unstructured":"B. A. Trakhtenbrot. Complexity of Algorithms and Computations, Course Notes, Novosibirsk, 1967. (Russian)"},{"key":"11_CR37","first-page":"232","volume-title":"Lecture Notes in Computer Science #32","author":"P. Emde Boas van","year":"1975","unstructured":"P. van Emde Boas. Ten years of speed-up, Proceedings of the Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science #32, Springer-Verlag, Berlin, 1975, 232\u2013237."},{"key":"11_CR38","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1090\/S0002-9939-1973-0312768-7","volume":"37","author":"P. Young","year":"1973","unstructured":"P. Young. Easy constructions in complexity theory: gap and speed-up theorems, Proc. Amer. Math. Soc. 37 (1973), 555\u2013563.","journal-title":"Proc. Amer. Math. Soc."},{"key":"11_CR39","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(93)90161-L","volume":"119","author":"M. Zimand","year":"1993","unstructured":"M. Zimand. If not empty, NP is topologically large, Theoret. Comput. Sci. 119 (1993), 293\u2013310.","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR40","unstructured":"M. Zimand. On the topological size of p-m-complete degrees, Theoret. Comput. Sci. (to appear)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:57:10Z","timestamp":1742597830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_48"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"30 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}