{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:07:44Z","timestamp":1725570464575},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175169"},{"type":"electronic","value":"9783642175176"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_7","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:13:41Z","timestamp":1291389221000},"page":"49-60","source":"Crossref","is-referenced-by-count":1,"title":["Satisfiability with Index Dependency"],"prefix":"10.1007","author":[{"given":"Hongyu","family":"Liang","sequence":"first","affiliation":[]},{"given":"Jing","family":"He","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.jcss.2008.11.001","volume":"75","author":"E. Allender","year":"2009","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer\u2019s theorem. J. Comput. System Sci.\u00a075(4), 245\u2013254 (2009)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"7_CR2","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett.\u00a08(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"7_CR4","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1090\/S0002-9939-1989-0955458-1","volume":"105","author":"I. Borosh","year":"1989","unstructured":"Borosh, I., Flahive, M., Rubin, D., Treybig, B.: A Sharp Bound for Solutions of Linear Diophantine Equations. Proceedings of the American Mathematical Society\u00a0105(4), 844\u2013846 (1989)","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(86)90138-X","volume":"58","author":"I. Borosh","year":"1986","unstructured":"Borosh, I., Flahive, M., Treybig, B.: Small solution of linear Diophantine equations. Discrete Mathematics\u00a058(3), 215\u2013220 (1986)","journal-title":"Discrete Mathematics"},{"issue":"116","key":"7_CR6","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1090\/S0025-5718-1971-0301909-X","volume":"25","author":"G.H. Bradley","year":"1971","unstructured":"Bradley, G.H.: Algorithms for Hermite and Smith Normal Matrices and Linear Diophantine Equations. Mathematics of Computation\u00a025(116), 897\u2013907 (1971)","journal-title":"Mathematics of Computation"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd ACM STOC, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Gebauer, H., Szab\u00f3, T., Tardos, G.: The local lemma is tight for SAT. CoRR (Computing Research Repository), arXiv:1006.0744 (2010)","DOI":"10.1137\/1.9781611973082.52"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-79719-7_10","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2008","author":"K. Georgiou","year":"2008","unstructured":"Georgiou, K., Papakonstantinou, P.A.: Complexity and algorithms for well-structured k-SAT instances. In: Kleine B\u00fcning, H., Zhao, X. (eds.) SAT 2008. LNCS, vol.\u00a04996, pp. 105\u2013118. Springer, Heidelberg (2008)"},{"issue":"4","key":"7_CR10","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1145\/321850.321857","volume":"21","author":"L. Henschen","year":"1974","unstructured":"Henschen, L., Wos, L.: Unit refutations and Horn sets. J. ACM\u00a021(4), 590\u2013605 (1974)","journal-title":"J. ACM"},{"issue":"1","key":"7_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0222015","volume":"22","author":"J. Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J., Savick\u00fd, P., Tuza, Z.: One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM J. Comput.\u00a022(1), 203\u2013210 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput.\u00a011(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Monien, B., Sudborough, I.H.: Bandwidth constrained NP-complete problems. In: Proceedings of the 13th ACM STOC, pp. 207\u2013217 (1981)","DOI":"10.1145\/800076.802474"},{"key":"7_CR15","volume-title":"Elementary number theory and its applications","author":"K.H. Rosen","year":"2005","unstructured":"Rosen, K.H.: Elementary number theory and its applications, 5th edn. Addison-Wesley, Reading (2005)","edition":"5"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"1","key":"7_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified satisfiability problem. Discrete Appl. Math.\u00a08(1), 85\u201389 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci.\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"7_CR19","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability Problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"issue":"1-3","key":"7_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(83)80027-8","volume":"59","author":"S. Yamasaki","year":"1983","unstructured":"Yamasaki, S., Doshita, S.: The satisfiability problem for the class consisting of Horn sentences and some non-Horn sentences in propositional logic. Infor. Control\u00a059(1-3), 1\u201312 (1983)","journal-title":"Infor. Control"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:49:30Z","timestamp":1559836170000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}