{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:36:25Z","timestamp":1787510185306,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_107","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:46:19Z","timestamp":1330177579000},"page":"311-324","source":"Crossref","is-referenced-by-count":7,"title":["Optimal approximations of complete sets"],"prefix":"10.1007","author":[{"given":"David A.","family":"Russo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"23_CR1","unstructured":"D.Z. Du, T. Isakowitz, and D.A. Russo, Structural properties of complexity cores, submitted for publication."},{"key":"23_CR2","volume-title":"Computers and Intractability","author":"M. Gary","year":"1979","unstructured":"M. Gary and D. Johnson, Computers and Intractability, W. H. Freeman, San Francisco (1979)."},{"key":"23_CR3","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley (1979)."},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF01699469","volume":"18","author":"K. Ko","year":"1985","unstructured":"K. Ko, Non-levelable sets and immune sets in the accepting density hierarchy in NP, Math. Systems Theory 18, (1985) 189\u2013205.","journal-title":"Math. Systems Theory"},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K. Ko","year":"1981","unstructured":"K. Ko and D. Moore, Completeness, approximation and density, SIAM J. Comput. 10, (1981) pp 787\u2013796.","journal-title":"SIAM J. Comput."},{"key":"23_CR6","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. J. Assoc. Comput. Mach. 22, (1975), 341\u2013345.","journal-title":"J. Assoc. Comput. Mach."},{"key":"23_CR7","volume-title":"With what frequency are apparently intractible problems difficult?","author":"A.R. Meyer","year":"1979","unstructured":"A.R. Meyer, and M.S. Paterson, With what frequency are apparently intractible problems difficult? Tech. Rep. TM-126, Laboratory for Computer Science, (1979) Massachusetts Institute of Technology, Cambridge, Ma."},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"P. Orponen, D.A. Russo, and U. Sch\u00f6ning, Optimal approximations and polynomially levelable sets, SIAM J. Comput., to appear.","DOI":"10.1137\/0215027"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/BFb0030328","volume":"176","author":"P. Orponen","year":"1984","unstructured":"P. Orponen and U. Sch\u00f6ning, The structure of polynomial complexity cores, Proc. 11th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 176 (1984), 452\u2013458.","journal-title":"Proc. 11th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science"},{"key":"23_CR10","unstructured":"D.A. Russo and P. Orponen, A duality between polynomial time computable subsets and complexity cores, submitted for publication."},{"key":"23_CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(85)90218-X","volume":"38","author":"O. Watanabe","year":"1985","unstructured":"O. Watanabe, On one-one polynomial time equivalence relations. Theoret. Comput. Sci. 38, (1985), 157\u2013165.","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"P. Young, Some structural properties of polynomial reducibilities, Proc. 15th Symp. Theory of Computing, (1983) pp 392\u2013401.","DOI":"10.1145\/800061.808770"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_107.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:28Z","timestamp":1605625828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_107","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}