{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:37:18Z","timestamp":1725514638365},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540693109"},{"type":"electronic","value":"9783540693116"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69311-6_11","type":"book-chapter","created":{"date-parts":[[2008,6,6]],"date-time":"2008-06-06T07:17:46Z","timestamp":1212736666000},"page":"79-88","source":"Crossref","is-referenced-by-count":0,"title":["NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT\u2009\u2265\u2009k ,r-UNLSAT\u2009\u2265\u2009k )"],"prefix":"10.1007","author":[{"given":"Tianyan","family":"Deng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daoyun","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","volume-title":"Introduction to Computational Complexity (Chinese)","author":"D. Du","year":"2004","unstructured":"Du, D., Ko, K.-I., Wang, J.: Introduction to Computational Complexity (Chinese). Higher Education Press, P.R.China (2004)"},{"key":"11_CR2","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2007","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Princeton University, Princeton (2007)"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/978-3-540-72504-6_56","volume-title":"Theory and Applications of Models of Computation","author":"Q. Zhang","year":"2007","unstructured":"Zhang, Q., Xu, D.: The Existence of Unsatisfiable Formulas in k-LCNF for k \u2265 3. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol.\u00a04484, pp. 616\u2013623. Springer, Heidelberg (2007)"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1018924526592","volume":"23","author":"G. Davydov","year":"1998","unstructured":"Davydov, G., Davydova, I., Kleine B\u00fcning, H.: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Annals of Mathematics and Artificial Intelligence\u00a023, 229\u2013245 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","volume":"289","author":"H. Fleischner","year":"2002","unstructured":"Fleischner, H., Kullmann, O., Szeider, S.: Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference. Theoretical Computer Science\u00a0289(1), 503\u2013516 (2002)","journal-title":"Theoretical Computer Science"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Porschen, S., Speckenmeyer, E.: Linear CNF formulas and satisfiability, Tech. Report zaik2006-520, University K\u00f6ln (2006)","DOI":"10.1007\/11814948_22"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/11814948_22","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"S. Porschen","year":"2006","unstructured":"Porschen, S., Speckenmeyer, E., Randerath, B.: On Linear CNF Formulas. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 212\u2013225. Springer, Heidelberg (2006)"},{"key":"11_CR8","unstructured":"Porschen, S., Speckenmeyer, E.: NP-completeness of SAT for restricted linear formulas classes. In: Proceedings of Guangzhou Symposium on Satisfiability in Logic-Based Modeling, vol.\u00a01, pp. 108\u2013121, pp. 111\u2013123 (1997)"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.C.: The complexity of theorem-proving procedures. In: Proc. 3rd ACM STOC, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69311-6_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:34:47Z","timestamp":1620002087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69311-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540693109","9783540693116"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69311-6_11","relation":{},"subject":[]}}