{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T07:13:21Z","timestamp":1761549201514,"version":"build-2065373602"},"reference-count":13,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T00:00:00Z","timestamp":1593388800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SAT"],"DOI":"10.3233\/sat-200125","type":"journal-article","created":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T14:07:39Z","timestamp":1592316459000},"page":"1-15","source":"Crossref","is-referenced-by-count":0,"title":["Backdoors into Two Occurrences"],"prefix":"10.1177","volume":"12","author":[{"given":"Jan","family":"Johannsen","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2020,6,29]]},"reference":[{"key":"10.3233\/SAT-200125_ref1","doi-asserted-by":"crossref","unstructured":"S.A.\u00a0Cook, The complexity of theorem-proving procedures, in: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp.\u00a0151\u2013158.","DOI":"10.1145\/800157.805047"},{"issue":"3","key":"10.3233\/SAT-200125_ref2","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(96)00028-5","article-title":"Variable and term removal from Boolean formulae","volume":"75","author":"Crama","year":"1997","journal-title":"Discrete Applied Mathematics"},{"key":"10.3233\/SAT-200125_ref3","first-page":"161","article-title":"Fixed-parameter tractability and completeness","volume":"87","author":"Downey","year":"1992","journal-title":"Congressus Numerantium"},{"key":"10.3233\/SAT-200125_ref4","unstructured":"J.\u00a0Flum and M.\u00a0Grohe, Parameterized Complexity Theory, Texts in Theoretical Computer Science, Springer, 2006."},{"key":"10.3233\/SAT-200125_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_15"},{"issue":"4","key":"10.3233\/SAT-200125_ref6","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"10.3233\/SAT-200125_ref7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1137\/0218026","article-title":"CNF-satisfiability test by counting and polynomial average time","volume":"18","author":"Iwama","year":"1989","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/SAT-200125_ref8","doi-asserted-by":"crossref","unstructured":"J.\u00a0Johannsen, Satisfiability problems complete for deterministic logarithmic space, in: 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), V.\u00a0Diekert and M.\u00a0Habib, eds, Lecture Notes in Computer Science, Vol.\u00a02996, 2004, pp.\u00a0317\u2013325.","DOI":"10.1007\/978-3-540-24749-4_28"},{"key":"10.3233\/SAT-200125_ref9","unstructured":"H.\u00a0Kleine B\u00fcning and T.\u00a0Lettmann, Propositional Logic: Deduction and Algorithms, Cambridge University Press, 1999."},{"issue":"7\u20138","key":"10.3233\/SAT-200125_ref10","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00236-007-0056-x","article-title":"Solving #SAT using vertex covers","volume":"44","author":"Nishimura","year":"2007","journal-title":"Acta Informatica"},{"key":"10.3233\/SAT-200125_ref11","unstructured":"N.\u00a0Nishimura, P.\u00a0Ragde and S.\u00a0Szeider, Detecting backdoor sets with respect to Horn and binary clauses, in: Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, 2004, pp.\u00a096\u2013103."},{"key":"10.3233\/SAT-200125_ref12","doi-asserted-by":"crossref","unstructured":"T.J.\u00a0Schaefer, The complexity of satisfiability problems, in: Proceedings of the 10th ACM Symposium on Theory of Computing, 1978, pp.\u00a0216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"10.3233\/SAT-200125_ref13","unstructured":"R.\u00a0Williams, C.\u00a0Gomes and B.\u00a0Selman, Backdoors to typical case complexity, in: Proceedings of the 18th International Joint Conference on Artificial Intelligence, G.\u00a0Gottlob and T.\u00a0Walsh, eds, 2003, pp.\u00a01173\u20131178."}],"container-title":["Journal on Satisfiability, Boolean Modeling and Computation"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SAT-200125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T07:08:26Z","timestamp":1761548906000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SAT-200125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,29]]},"references-count":13,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,6,29]]}},"URL":"https:\/\/doi.org\/10.3233\/sat-200125","relation":{},"ISSN":["1574-0617"],"issn-type":[{"type":"electronic","value":"1574-0617"}],"subject":[],"published":{"date-parts":[[2020,6,29]]}}}