{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:52:59Z","timestamp":1764557579836,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Sabbatical visit support from ETH Zurich\u2019s Department of Computer Science"},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-2006496"],"award-info":[{"award-number":["CCF-2006496"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Prog Artif Intell"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s13748-021-00234-6","type":"journal-article","created":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T15:02:46Z","timestamp":1615647766000},"page":"297-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Existence versus exploitation: the opacity of backdoors and backbones"],"prefix":"10.1007","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0659-5204","authenticated-orcid":false,"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3704-1060","authenticated-orcid":false,"given":"David E.","family":"Narv\u00e1ez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,13]]},"reference":[{"key":"234_CR1","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1613\/jair.1.11741","volume":"66","author":"C Ans\u00f3tegui","year":"2019","unstructured":"Ans\u00f3tegui, C., Bonet, M., Gir\u00e1ldez-Cru, J., Levy, J., Simon, L.: Community structures in industrial SAT instances. J. Artif. Intell. Res. 66, 443\u2013472 (2019)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"234_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/S0097539792228289","volume":"23","author":"M Bellare","year":"1994","unstructured":"Bellare, M., Goldwasser, S.: The complexity of decision versus search. SIAM J. Comput. 23(1), 97\u2013119 (1994)","journal-title":"SIAM J. Comput."},{"key":"234_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P.: Relationship between density and deterministic complexity of NP-complete languages. In: Proceedings of the 5th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, July 1978, vol. 62, pp. 63\u201371. Springer (1978)","DOI":"10.1007\/3-540-08860-1_6"},{"key":"234_CR4","unstructured":"Borodin, A., Demers, A.: Some comments on functional self-reducibility and the NP hierarchy. Technical Report TR 76-284, Department of Computer Science, Cornell University, Ithaca, NY, July (1976)"},{"key":"234_CR5","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Hitchcock, J.: NP-hard sets are exponentially dense unless coNP$$\\,\\subseteq \\,$$NP\/poly. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, June 2008, pp. 1\u20137. IEEE Computer Society Press (2008)","DOI":"10.1109\/CCC.2008.21"},{"issue":"1","key":"234_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J Cai","year":"2005","unstructured":"Cai, J., Chakaravarthy, V., Hemaspaandra, L., Ogihara, M.: Competing provers yield improved Karp\u2013Lipton collapse results. Inf. Comput. 198(1), 1\u201323 (2005)","journal-title":"Inf. Comput."},{"key":"234_CR7","doi-asserted-by":"crossref","unstructured":"Chen, W., Whitley, D.: Decomposing SAT instances with pseudo backbones. In: Proceedings of the 17th European Conference on Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, March 2017, vol. 10197, pp. 75\u201390. Springer (2017)","DOI":"10.1007\/978-3-319-55453-2_6"},{"key":"234_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, May 1971, pp. 151\u2013158. ACM Press (1971)","DOI":"10.1145\/800157.805047"},{"key":"234_CR9","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"7","author":"M Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Commun. ACM 7, 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"issue":"3","key":"234_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM 7(3), 201\u2013215 (1960)","journal-title":"J. ACM"},{"issue":"4","key":"234_CR11","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10472-014-9407-9","volume":"70","author":"B Dilkina","year":"2014","unstructured":"Dilkina, B., Gomes, C., Sabharwal, A.: Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search. Ann. Math. Artif. Intell. 70(4), 399\u2013431 (2014)","journal-title":"Ann. Math. Artif. Intell."},{"key":"234_CR12","unstructured":"Dowling, W., Gallier, J.: Linear-time algorithms for testing the satisfiability of propositional Horn formulae. J. Log. Program. 1(3), 267\u2013284 (1984)"},{"key":"234_CR13","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Krohmer, A., Rothenberger, R., Sutton, A.: Phase transitions for scale-free SAT formulas. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, February 2017, pp. 3893\u20133899. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.11133"},{"issue":"1","key":"234_CR14","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/3319627.3319636","volume":"50","author":"W Gasarch","year":"2019","unstructured":"Gasarch, W.: The third P =? NP poll. SIGACT News 50(1), 38\u201359 (2019)","journal-title":"SIGACT News"},{"key":"234_CR15","unstructured":"Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., \u017divn\u00fd, S.: Backdoors into heterogeneous classes of SAT and CSP. \u00a0J. Comput. Syst. Sci. 85, 38\u201356 (2017)"},{"issue":"1\u20133","key":"234_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J Hartmanis","year":"1988","unstructured":"Hartmanis, J., Hemachandra, L.: Complexity classes without machines: on complete languages for UP. Theor. Comput. Sci. 58(1\u20133), 129\u2013142 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"234_CR17","first-page":"1","volume":"12","author":"E Hemaspaandra","year":"2020","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Menton, C.: Search versus decision for election manipulation problems. ACM Trans. Comput. 12, 1\u201342 (2020)","journal-title":"ACM Trans. Comput."},{"key":"234_CR18","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L.: Computational social choice and computational complexity: BFFs? In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, February 2018, pp. 7971\u20137977. AAAI Press (2018)","DOI":"10.1609\/aaai.v32i1.12220"},{"key":"234_CR19","unstructured":"Hemaspaandra, L., Narv\u00e1ez, D.: The opacity of backbones. Technical Report, Computing Research Repository, June 2016. Revised, January (2017). arXiv:1606.03634"},{"key":"234_CR20","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Narv\u00e1ez, D.: The opacity of backbones. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, February 2017, pp. 3900\u20133906. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.11134"},{"key":"234_CR21","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Narv\u00e1ez, D.: Existence versus exploitation: the opacity of backbones and backdoors under a weak assumption. In: Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science. Lecture Notes in Computer Science, January 2019, vol. 11376, pp. 247\u2013259. Springer (2019)","DOI":"10.1007\/978-3-030-10801-4_20"},{"key":"234_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04880-1","volume-title":"The Complexity Theory Companion","author":"L Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer, Berlin (2002)"},{"issue":"4","key":"234_CR23","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/2421119.2421135","volume":"43","author":"L Hemaspaandra","year":"2012","unstructured":"Hemaspaandra, L., Williams, R.: An atypical survey of typical-case heuristic algorithms. SIGACT News 43(4), 71\u201389 (2012)","journal-title":"SIGACT News"},{"issue":"5","key":"234_CR24","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01184814","volume":"29","author":"L Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L., Zimand, M.: Strong self-reducibility precludes strong immunity. Math. Syst. Theory 29(5), 535\u2013548 (1996)","journal-title":"Math. Syst. Theory"},{"key":"234_CR25","unstructured":"Kilby, P., Slaney, J., Thi\u00e9baux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: Proceedings of the 20th National Conference on Artificial Intelligence, July 2005, pp. 1368\u20131373. AAAI Press (2005)"},{"key":"234_CR26","doi-asserted-by":"crossref","unstructured":"Kochemazov, S., Zaikin, O.: ALIAS: A modular tool for finding backdoors for SAT. In: Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, June 2018, vol. 10929, pp. 419\u2013427. Springer (2018)","DOI":"10.1007\/978-3-319-94144-8_25"},{"issue":"2","key":"234_CR27","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S Mahaney","year":"1982","unstructured":"Mahaney, S.: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. J. Comput. Syst. Sci. 25(2), 130\u2013143 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"234_CR28","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Detecting backdoor sets with respect to Horn and binary clauses. In: Informal Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, May 2004, pp. 96\u2013103 (2004)"},{"key":"234_CR29","volume-title":"Computational Complexity","author":"C Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Boston (1994)"},{"key":"234_CR30","unstructured":"Rothe, J.: Complexity of certificates, heuristics, and counting types, with applications to cryptography and circuit theory. Habilitation thesis, Friedrich-Schiller-Universit\u00e4t Jena, Institut f\u00fcr Informatik, Jena, Germany, June (1999)"},{"key":"234_CR31","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing, May 1978, pp. 216\u2013226. ACM Press (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1","key":"234_CR32","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01704904","volume":"19","author":"U Sch\u00f6ning","year":"1986","unstructured":"Sch\u00f6ning, U.: Complete sets and closeness to complexity classes. Math. Syst. Theory 19(1), 29\u201342 (1986)","journal-title":"Math. Syst. Theory"},{"key":"234_CR33","doi-asserted-by":"crossref","unstructured":"Semenov, A., Zaikin, O., Otpuschennikov, I., Kochemazov, S., Ignatiev, A.: On cryptographic attacks using backdoors for SAT. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, February 2018, pp. 6641\u20136648. AAAI Press (2018)","DOI":"10.1609\/aaai.v32i1.12205"},{"issue":"1\u20133","key":"234_CR34","first-page":"73","volume":"35","author":"S Szeider","year":"2005","unstructured":"Szeider, S.: Backdoor sets for DLL subsolvers. J. Autom. Reason. 35(1\u20133), 73\u201388 (2005)","journal-title":"J. Autom. Reason."},{"key":"234_CR35","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G Tardos","year":"1989","unstructured":"Tardos, G.: Query complexity, or why is it difficult to separate NP$${\\rm }^{A}{}\\cap \\,$$coNP$${\\rm }^{A}$$ from P$${\\rm {{}}}^{A}$$ by random oracles $${A}$$. Combinatorica 9, 385\u2013392 (1989)","journal-title":"Combinatorica"},{"issue":"1","key":"234_CR36","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L Valiant","year":"1976","unstructured":"Valiant, L.: The relative complexity of checking and evaluating. Inf. Process. Lett. 5(1), 20\u201323 (1976)","journal-title":"Inf. Process. Lett."},{"key":"234_CR37","unstructured":"Willams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, August 2003, pp. 1173\u20131178. Morgan Kaufmann (2003)"}],"container-title":["Progress in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13748-021-00234-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13748-021-00234-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13748-021-00234-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T11:07:59Z","timestamp":1671620879000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13748-021-00234-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,13]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["234"],"URL":"https:\/\/doi.org\/10.1007\/s13748-021-00234-6","relation":{},"ISSN":["2192-6352","2192-6360"],"issn-type":[{"type":"print","value":"2192-6352"},{"type":"electronic","value":"2192-6360"}],"subject":[],"published":{"date-parts":[[2021,3,13]]},"assertion":[{"value":"14 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}