{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:36Z","timestamp":1725663156124},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540502418"},{"type":"electronic","value":"9783540459606"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50241-6_43","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:18:41Z","timestamp":1330201121000},"page":"273-280","source":"Crossref","is-referenced-by-count":1,"title":["Complexity cores and hard-to-prove formulas"],"prefix":"10.1007","author":[{"given":"Uwe","family":"Sch\u00f6ning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"3","key":"19_CR1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1008311.1008313","volume":"6","author":"S.A. Cook","year":"1974","unstructured":"S.A. Cook and R. Reckow, On the length of proofs in the propositional calculus, Proc. 6th ACM STOC, 1974, 135\u2013148. Corrections in SIGACT News 6, No. 3 (1974), 15\u201322.","journal-title":"Corrections in SIGACT News"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedures, Proc. 3rd ACM STOC, 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken, The intractability of resolution, Theor. Comput. Sci. 39 (1985), 297\u2013308.","journal-title":"Theor. Comput. Sci."},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"A. Urquhart, Hard examples for resolution, Journ. Assoc. Comput. Mach. 34 (1987), 209\u2013219.","journal-title":"Journ. Assoc. Comput. Mach."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"G. S. Tseitin, On the complexity of derivations in the propositional calculus, Structures in Constructive Math. Logic, Part II, A.O. Slisenko (ed.), 1968, 115\u2013125.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Z. Galil, On the validity and complexity of bounded resolution, Proc. 7th ACM STOC, 1975, 72\u201382.","DOI":"10.1145\/800116.803755"},{"key":"19_CR7","unstructured":"Z. Galil, On enumeration procedures for theorem proving and integer programming, 3rd ICALP 1976, Edinburgh University Press, S. Michaelson and R. Milner (eds.), 355\u2013381."},{"key":"19_CR8","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, Journ. Assoc. Mach. 22 (1975), 341\u2013345.","journal-title":"Journ. Assoc. Mach."},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/2455.214111","volume":"32","author":"S. Even","year":"1985","unstructured":"S. Even, A.L. Selman, and Y. Yacobi, Hard-core theorems for complexity classes, Journ. Assoc. Comput. Mach. 32 (1985), 205\u2013217.","journal-title":"Journ. Assoc. Comput. Mach."},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(86)80024-9","volume":"70","author":"P. Orponen","year":"1986","unstructured":"P. Orponen and U. Sch\u00f6ning, The density and complexity of polynomial cores for intractable sets, Information and Control 70 (1986), 54\u201368.","journal-title":"Information and Control"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1145\/28869.28880","volume":"34","author":"D.Z. Du","year":"1987","unstructured":"D.Z. Du and R.V. Book, The existence and density of generalized complexity cores, Journ. Assoc. Comput. Mach. 34 (1987), 718\u2013730.","journal-title":"Journ. Assoc. Comput. Mach."},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"B. Krishnamurthy and R.N. Moll, Examples of hard tautologies in the propositional calculus, Proc. 13th ACM STOC, 1981, 28\u201337.","DOI":"10.1145\/800076.802454"},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets, SIAM Journ. on Computing 6 (1977), 305\u2013322.","journal-title":"SIAM Journ. on Computing"},{"key":"19_CR14","unstructured":"H. Kleine B\u00fcning, Some remarks on polynomial algorithms for the satisfiability problem, manuscript 1981."},{"key":"19_CR15","unstructured":"A.R. Meyer and M.S. Paterson, With what frequency are apparently intractable problems difficult?, Techn. Report, MIT\/LCS\/TM-126, Feb. 1979."},{"key":"19_CR16","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/0215027","volume":"15","author":"P. Orponen","year":"1986","unstructured":"P. Orponen, D.A. Russo, and U. Sch\u00f6ning, Optimal approximations and polynomially levelable sets, SIAM Journ. on Computing 15 (1986), 399\u2013408.","journal-title":"SIAM Journ. on Computing"}],"container-title":["Lecture Notes in Computer Science","CSL '87"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50241-6_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:17:45Z","timestamp":1605647865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50241-6_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540502418","9783540459606"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-50241-6_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}