{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:11Z","timestamp":1725663371667},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_149","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:37:59Z","timestamp":1330209479000},"page":"381-392","source":"Crossref","is-referenced-by-count":2,"title":["Improving known solutions is hard"],"prefix":"10.1007","author":[{"given":"Desh","family":"Ranjan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suresh","family":"Chari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj","family":"Rohatgi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(80)90006-7","volume":"12","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi. Toward a unified approach for the classification of NP-complete problems. Theoretical Computer Science, 12:83\u201396, 1980.","journal-title":"Theoretical Computer Science"},{"key":"29_CR2","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D. Johnson. Computers and Intractability. Freeman, San Francisco, 1979."},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00ed\u010dek, P. Pudl\u00e1k, and J. Sgall. Interactive Computation of Optimal Solutions. In Mathematical Foundations of Computer Science, Springer-Verlag LNCS #452, pages 48\u201360, 1990.","DOI":"10.1007\/BFb0029595"},{"key":"29_CR4","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"M.W. Krentel. The Complexity of Optimization. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"29_CR5","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou. On the complexity of unique solutions. Journal of the ACM, 31:392\u2013400, 1984.","journal-title":"Journal of the ACM"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes. In 20 th ACM Symposium on Theory of Computing, pages 229\u2013234, 1988.","DOI":"10.1145\/62212.62233"},{"issue":"1","key":"29_CR7","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U. Sch\u00f6ning","year":"1989","unstructured":"U. Sch\u00f6ning. Probabilistic complexity classes and lowness. Journal of Computer and System Sciences, 39(1):84\u2013100, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"29_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(1):85\u201393, 1986.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"29_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C. Yap","year":"1983","unstructured":"C. Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science, 26(3):287\u2013300, 1983.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_149.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:15Z","timestamp":1605646395000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_149","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}