{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T00:27:04Z","timestamp":1649032024086},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,6,1]],"date-time":"1993-06-01T00:00:00Z","timestamp":738892800000},"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":[[1993,6]]},"DOI":"10.1007\/bf01200119","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T15:52:00Z","timestamp":1108741920000},"page":"168-185","source":"Crossref","is-referenced-by-count":3,"title":["Improving known solutions is hard"],"prefix":"10.1007","volume":"3","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","reference":[{"key":"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, andM. Protasi. Toward a unified approach for the classification of NP-complete problems.Theoretical Computer Science 12:83?96, 1980.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"CR2","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 oracle,P A ?N P A ?co-N P A .SIAM Journal on Computing, 10(1):96?112, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"CR3","unstructured":"S. Buss.Bounded Arithmetic. Studies in Proof Theory 3. Bibliopolis, Naples, 1986."},{"key":"CR4","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey andD. Johnson.Computers and Intractability. Freeman, San Fransisco, 1979."},{"key":"CR5","unstructured":"J. Kraj\u00ed?ek, P. Pudl\u00e1k, and J. Sgall. Interactive Computation of Optimal Solutions. InMathematical Foundations of Computer Science, Springer-VerlagLNCS #452, 1990."},{"key":"CR6","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?509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR7","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?400, 1984.","journal-title":"Journal of the ACM"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, Approximation and Complexity Classes. In20 th ACM Symposium on Theory of Computing, pages 229?234, 1988.","DOI":"10.1145\/62212.62233"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"D. Ranjan, S. Chari, and P. Rohtagi. Improving known solutions is hard. InProceedings of the 18 th ICALP, pages 381?392. Springer-Verlag, 1991. Lecture Notes in Computer Science # 510.","DOI":"10.1007\/3-540-54233-7_149"},{"issue":"1","key":"CR10","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. Probabalistic complexity classes and lowness.Journal of Computer and System Sciences, 39(1):84?100, 1989.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"CR11","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 andV.V. Vazirani. NP is as easy as detecting unique solutions.Theoretical Computer Science 47(1):85?93, 1986.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"CR12","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?300, 1983.","journal-title":"Theoretical Computer Science"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200119.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200119\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:13:56Z","timestamp":1586121236000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["BF01200119"],"URL":"https:\/\/doi.org\/10.1007\/bf01200119","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}