{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:16:53Z","timestamp":1740097013378,"version":"3.37.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_27","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"351-364","source":"Crossref","is-referenced-by-count":0,"title":["The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits"],"prefix":"10.1007","author":[{"given":"Konrad","family":"Schwerdtfeger","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with boolean blocks, part i: Posts lattice with applications to complexity theory. In: SIGACT News (2003)"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Fu, Z., Malik, S.: Extracting logic circuit structure from conjunctive normal form descriptions. In: 20th International Conference on VLSI Design, Held Jointly with 6th International Conference on Embedded Systems, pp. 37\u201342. IEEE (2007)","DOI":"10.1109\/VLSID.2007.81"},{"issue":"6","key":"27_CR3","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P. Gopalan","year":"2009","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E., Papadimitriou, C.H.: The connectivity of boolean satisfiability: Computational and structural dichotomies. SIAM J. Comput.\u00a038(6), 2330\u20132355 (2009), http:\/\/dx.doi.org\/10.1137\/07070440X","journal-title":"SIAM J. Comput."},{"issue":"12-14","key":"27_CR4","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T. Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci.\u00a0412(12-14), 1054\u20131065 (2011), http:\/\/dx.doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theor. Comput. Sci."},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-642-19222-7_7","volume-title":"Combinatorial Algorithms","author":"M. Kami\u0144ski","year":"2011","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Shortest paths between shortest paths and independent sets. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 56\u201367. Springer, Heidelberg (2011)"},{"issue":"1","key":"27_CR6","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01744287","volume":"13","author":"H.R. Lewis","year":"1979","unstructured":"Lewis, H.R.: Satisfiability problems for propositional calculi. Mathematical Systems Theory\u00a013(1), 45\u201353 (1979)","journal-title":"Mathematical Systems Theory"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-72788-0_20","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"K. Makino","year":"2007","unstructured":"Makino, K., Tamaki, S., Yamamoto, M.: On the boolean connectivity problem for horn relations. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol.\u00a04501, pp. 187\u2013200. Springer, Heidelberg (2007)"},{"issue":"4","key":"27_CR8","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1255443.1255445","volume":"54","author":"E. Maneva","year":"2007","unstructured":"Maneva, E., Mossel, E., Wainwright, M.J.: A new look at survey propagation and its generalizations. Journal of the ACM (JACM)\u00a054(4), 17 (2007)","journal-title":"Journal of the ACM (JACM)"},{"issue":"19","key":"27_CR9","doi-asserted-by":"publisher","first-page":"197205","DOI":"10.1103\/PhysRevLett.94.197205","volume":"94","author":"M. M\u00e9zard","year":"2005","unstructured":"M\u00e9zard, M., Mora, T., Zecchina, R.: Clustering of solutions in the random satisfiability problem. Physical Review Letters\u00a094(19), 197205 (2005)","journal-title":"Physical Review Letters"},{"issue":"10","key":"27_CR10","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.ipl.2012.02.002","volume":"112","author":"T. Michael","year":"2012","unstructured":"Michael, T.: On the applicability of post\u2019s lattice. Information Processing Letters\u00a0112(10), 386\u2013391 (2012)","journal-title":"Information Processing Letters"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic(AM-5), vol.\u00a05. Princeton University Press (1941)","DOI":"10.1515\/9781400882366"},{"key":"27_CR12","unstructured":"Reith, S., Wagner, K.W.: The complexity of problems defined by Boolean circuits (2000)"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"27_CR14","unstructured":"Schnoor, H.: Algebraic techniques for satisfiability problems. Ph.D. thesis, Universit\u00e4t Hannover (2007)"},{"key":"27_CR15","unstructured":"Schwerdtfeger, K.W.: A computational trichotomy for connectivity of boolean satisfiability. ArXiv CoRR abs\/1312.4524 (2013), extended version of a paper submitted to the JSAT Journal, http:\/\/arxiv.org\/abs\/1312.4524"},{"key":"27_CR16","unstructured":"Schwerdtfeger, K.W.: The connectivity of boolean satisfiability: Dichotomies for formulas and circuits. ArXiv CoRR abs\/1312.6679 (2013), extended version of this paper, http:\/\/arxiv.org\/abs\/1312.6679"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc. (1999)","DOI":"10.1007\/978-3-662-03927-4"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Wu, C.A., Lin, T.H., Lee, C.C., Huang, C.Y.R.: Qutesat: a robust circuit-based sat solver for complex circuit structure. In: Proceedings of the Conference on Design, Automation and Test in Europe, EDA Consortium, pp. 1313\u20131318 (2007)","DOI":"10.1109\/DATE.2007.364479"},{"issue":"1-3","key":"27_CR19","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.dam.2004.06.028","volume":"149","author":"I.E. Zverovich","year":"2005","unstructured":"Zverovich, I.E.: Characterizations of closed classes of boolean functions in terms of forbidden subfunctions and post classes. Discrete Appl. Math.\u00a0149(1-3), 200\u2013218 (2005), http:\/\/dx.doi.org\/10.1016\/j.dam.2004.06.028","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T01:24:22Z","timestamp":1565486662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}