{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:34Z","timestamp":1787340574883,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>For a simple parameterized model of conjunctive normal form predicates, we show that a simplified version of the Davis\u2013Putnam procedure can, for many values of the parameters, solve the satisfiability problem in polynomial average time. Let v be the number of variables, $t(v)$ the number of clauses in a predicate, and $p(v)$ the probability that a given literal appears in a clause ($p(v)$ is the same for all literals). Let $\\varepsilon $ be any small positive constant and n any large positive integer. Then a version of the Davis\u2013Putnam procedure that uses only backtracking and the pure literal rule uses average time that is polynomial in the problem size when any of the following conditions are true for large v. (1) $t(v) \\leqq n\\ln v$; (2) $t(v) \\geqq \\exp (\\varepsilon v)$; (3) $p(v) \\geqq \\varepsilon $; or (4) $p(v) \\leqq n (\\ln v\/ v)^{3\/2} $. Until recently the best previous bounds for cases (1) and (4) were $t(v) \\leqq (\\ln\\ln v)\/(\\ln3)$ and $p(v) \\leqq \\exp ( - v\\ln \\ln v)$. These results show that the problem types for which the pure literal rule works well are quite different from those for which backtracking works well. Our present knowledge suggests this random problem sets with $t(v)$ somewhat larger than v and with $p(v)$ somewhat larger than $v^{ - 1} $ are particularly difficult to solve.<\/jats:p>","DOI":"10.1137\/0214067","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"943-953","source":"Crossref","is-referenced-by-count":40,"title":["The Pure Literal Rule and Polynomial Average Time"],"prefix":"10.1137","volume":"14","author":[{"given":"Paul Walton","family":"Purdom, Jr.","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cynthia A.","family":"Brown","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0210043"},{"key":"R2","unstructured":"Cynthia A. Brown, Paul Walton Purdom, Jr.,  How to search efficiently,  Proc. Seventh International Joint Conference on Artificial Intelligence,  1981,  588\u2013594"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"R5","unstructured":"John Franco,  Average analysis of the pure literal heuristic, Report, CES-81-4, Case Institute of Technology, Cleveland, OH"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90017-3"},{"key":"R7","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R8","unstructured":"Allen Goldberg,  On the complexity of the satisfiability problem, Report, 16, Courant Computer Science, New York Univ., New York"},{"key":"R9","unstructured":"Allen Goldberg,  Average case complexity of the satisfiability problem,  Proc. Fourth Workshop on Automated Deduction,  1979,  1\u20136"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90110-7"},{"key":"R11","unstructured":"Daniel H. Greene, Donald E. Knuth, Mathematics for the analysis of algorithms, Progress in Computer Science, Vol. 1, Birkh\u00e4user Boston, Mass., 1981, 107\u201383c:680450481.68042"},{"key":"R12","unstructured":"Burkhard Monien, Ewald Speckenmeyer,  Three-satisfiability is testable in  O(1.62r) steps, Report, 3, Theoretical Informatics Series, Univ. Paderborn,  1979"},{"key":"R13","first-page":"309","volume":"4","author":"Purdom, Jr. Paul Walton","year":"1982","journal-title":"IEEETPAMI"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(83)80007-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0212049"},{"key":"R16","unstructured":"Paul Walton Purdom, Jr., Cynthia A. Brown,  Polynomial average-time satisfiability problems, Report, 118, Indiana University Computer Science, Bloomington, IN"},{"key":"R17","unstructured":"Paul Walton Purdom, Jr., Cynthia A. Brown,  Evaluating search methods analytically,  National Conference on Artificial Intelligence,  1982,  124\u2013127"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288958"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:04Z","timestamp":1787337604000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214067"],"URL":"https:\/\/doi.org\/10.1137\/0214067","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}