{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:37Z","timestamp":1742617117715,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"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-59042-0_108","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:53Z","timestamp":1330275593000},"page":"597-608","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Resource-bounded instance complexity"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kummer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"52_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural complexity I, II","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar, J. Diaz, J. Gabarr\u00f3. Structural complexity I, II. Spinger-Verlag, Berlin, 1988, 1990."},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P. Orponen. Random strings make hard instances. In: Proceedings Structure in Complexity Theory, Ninth Annual Conference, 217\u2013222, 1994.","DOI":"10.1109\/SCT.1994.315802"},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computation. In: Proc. 24th IEEE Symp. Foundations of Computer Science, pp. 439\u2013445, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"52_CR4","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/S0022-0000(05)80006-6","volume":"48","author":"S. Homer","year":"1994","unstructured":"S. Homer, L. Longpr\u00e9. On reductions of NP sets to sparse sets. Journal of Computer and System Sciences 48, 324\u2013336, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"K. Ko. A note on the instance complexity of pseudorandom sets. In: Proceedings Structure in Complexity Theory, Seventh Annual Conference, pp. 327\u2013337, 1992.","DOI":"10.1109\/SCT.1992.215407"},{"key":"52_CR6","series-title":"Lecture Notes in Computer Science 223","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/3-540-16486-3_99","volume-title":"Structure in Complexity Theory","author":"K. Ko","year":"1986","unstructured":"K. Ko, P. Orponen, U. Sch\u00f6ning, O. Watanabe. What is a hard instance of a computational problem? In: Structure in Complexity Theory (Ed. A. Selman), pp. 197\u2013217, Lecture Notes in Computer Science 223, Springer-Verlag, Berlin, 1986."},{"key":"52_CR7","unstructured":"M. Kummer. Kolmogorov complexity and instance complexity of recursively enumerable sets. Submitted for publication."},{"key":"52_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An introduction to Kolmogorov complexity and its applications","author":"M. Li","year":"1993","unstructured":"M. Li, P. Vit\u00e1nyi. An introduction to Kolmogorov complexity and its applications. Springer-Verlag, Berlin, 1993."},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"L. Longpr\u00e9, O. Watanabe. On symmetry of information and polynomial time invertibility. Manuscript, 1993.","DOI":"10.1007\/3-540-56279-6_93"},{"key":"52_CR10","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 classes, SIAM J. Comput. 19:1100\u20131131, 1990.","journal-title":"SIAM J. Comput."},{"key":"52_CR11","first-page":"392","volume-title":"Lecture Notes in Computer Science 629","author":"E. Mayordomo","year":"1992","unstructured":"E. Mayordomo. Almost every set in exponential time is p-bi-immune. In: Seventeeth International Symposium on Mathematical Foundations of Computer Science, pp. 392\u2013400, Lecture Notes in Computer Science 629, Springer-Verlag, Berlin, 1992."},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"A. Naik, M. Ogiwara, A. Selman. P-selective sets, and reducing search to decision vs. self-reducibility. In: Proceedings Structure in Complexity Theory, Eighth Annual Conference, pp. 52\u201364, 1993.","DOI":"10.1109\/SCT.1993.336541"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"P. Orponen. On the instance complexity of NP-hard problems. In: Proceedings Structure in Complexity Theory, Fifth Annual Conference, pp. 20\u201327, 1990.","DOI":"10.1109\/SCT.1990.113951"},{"key":"52_CR14","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/174644.174648","volume":"41","author":"P. Orponen","year":"1994","unstructured":"P. Orponen, K. Ko, U. Sch\u00f6ning, O. Watanabe. Instance complexity. J. of the ACM 41:96\u2013121, 1994.","journal-title":"J. of the ACM"},{"key":"52_CR15","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Math. Systems Theory 13:55\u201365, 1979.","journal-title":"Math. Systems Theory"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity theoretic approach to randomness. In: Proc. 15th ACM Symp. Theory of Computing, pp. 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_108","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_108"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_108","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":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}