{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:47:24Z","timestamp":1725472044794},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_31","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"346-357","source":"Crossref","is-referenced-by-count":12,"title":["The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies"],"prefix":"10.1007","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[]},{"given":"Elitza N.","family":"Maneva","sequence":"additional","affiliation":[]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proc. 10th ACM Symp. Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences\u00a051, 511\u2013522 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR3","volume-title":"SIAM Monographs on Disc. Math.","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classification of Boolean constraint satisfaction problems. In: SIAM Monographs on Disc. Math., vol.\u00a07, SIAM, Philadelphia (2001)"},{"issue":"6","key":"31_CR4","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.: The approximability of constraint satisfaction problems. SIAM J. Comput.\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"31_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125(1), 1\u201312 (1996)","journal-title":"Information and Computation"},{"issue":"1","key":"31_CR6","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM J. Comput.\u00a028(1), 152\u2013163 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"31_CR7","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/S0890-5401(03)00037-3","volume":"187","author":"L. Kirousis","year":"2003","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. Information and Computation\u00a0187(1), 20\u201339 (2003)","journal-title":"Information and Computation"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proc. 43rd IEEE Symp. Foundations of Computer Science, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Creignou, N., Zanuttini, B.: A complete classification of the complexity of propositional abduction. SIAM Journal on Computing (to appear, 2006)","DOI":"10.1137\/S0097539704446311"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., Naor, A., Peres, Y.: Rigorous location of phase transitions in hard optimization problems. Nature\u00a0435, 759\u2013764 (2005)","journal-title":"Nature"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"M\u00e9zard, M., Zecchina, R.: Random k-satisfiability: from an analytic solution to an efficient algorithm. Phys. Rev.\u00a0E 66 (2002)","DOI":"10.1103\/PhysRevE.66.056126"},{"key":"31_CR12","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M. M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science\u00a0297, 812 (2002)","journal-title":"Science"},{"key":"31_CR13","unstructured":"Maneva, E., Mossel, E., Wainwright, M.J.: A new look at survey propagation and its generalizations. In: Proc. 16th ACM-SIAM Symp. Discrete Algorithms, 1089\u20131098, pp. 1089\u20131098 (2005)"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Mora, T., M\u00e9zard, M., Zecchina, R.: Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. ( in press, 2005)","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. In: 38th ACM Symp. Theory of Computing (2006)","DOI":"10.1145\/1132516.1132537"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 1993, AMS (1996)","DOI":"10.1090\/dimacs\/026\/25"},{"key":"31_CR17","unstructured":"Achlioptas, D., Beame, P., Molloy, M.: Exponential bounds for DPLL below the satisfiability threshold. In: Proc. 15th ACM-SIAM Symp. Discrete Algorithms, pp. 132\u2013133 (2004)"},{"issue":"1","key":"31_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, Part II: constraint satisfaction problems. ACM SIGACT-Newsletter\u00a035(1), 22\u201335 (2004)","journal-title":"ACM SIGACT-Newsletter"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Hearne, R., Demaine, E.: The Nondeterministic Constraint Logic model of computation: Reductions and applications. In: 29th Intl. Colloquium on Automata, Languages and Programming, pp. 401\u2013413 (2002)","DOI":"10.1007\/3-540-45465-9_35"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:48Z","timestamp":1619507988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11786986_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}