{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:48:10Z","timestamp":1751582890021,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,4,16]],"date-time":"2010-04-16T00:00:00Z","timestamp":1271376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1007\/s11786-010-0036-3","type":"journal-article","created":{"date-parts":[[2010,4,15]],"date-time":"2010-04-15T06:19:35Z","timestamp":1271312375000},"page":"421-431","source":"Crossref","is-referenced-by-count":1,"title":["A Randomized Algorithm for 3-SAT"],"prefix":"10.1007","volume":"3","author":[{"given":"Subhas Kumar","family":"Ghosh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janardan","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,4,16]]},"reference":[{"issue":"3","key":"36_CR1","doi-asserted-by":"crossref","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. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"36_CR2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Brueggemann","year":"2004","unstructured":"Brueggemann T., Kern W.: An improved deterministic local search algorithm for 3-SAT. Theor. Comput. Sci. 329(1\u20133), 303\u2013313 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"36_CR3","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C. Calabro","year":"2008","unstructured":"Calabro C., Impagliazzo R., Kabanets V., Paturi R.: The complexity of unique k-SAT: an isolation lemma for k-CNFs. J. Comput. Syst. Sci. 74(3), 386\u2013393 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: STOC \u201971: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM Press, New York (1971)","DOI":"10.1145\/800157.805047"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Dantsin, E.: Two propositional proof systems based on the splitting method. Zapis. Nauch. Semin. LOMI 105, 24\u201344 (1981) (in Russian). English translation in J. Soviet Math. 22(3), 1293\u20131305 (1983)","DOI":"10.1007\/BF01084392"},{"issue":"1","key":"36_CR6","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"Dantsin E., Goerdt A., Hirsch E.A., Kannan R., Kleinberg J., Papadimitriou C., Raghavan P., Sch\u00f6ning U.: A deterministic (2 \u2212 2\/(k\u00a0+ 1)) n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289(1), 69\u201383 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"36_CR7","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis M., Logemann G., Loveland D.: A machine program for theorem-proving. Commun. ACM 5(7), 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"key":"36_CR8","volume-title":"An Introduction to Probability Theory and Its Applications, vol. 2","author":"W. Feller","year":"1971","unstructured":"Feller W.: An Introduction to Probability Theory and Its Applications, vol. 2, 2nd edn. Wiley, New York (1971)","edition":"2"},{"issue":"2","key":"36_CR9","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/3212033","volume":"4","author":"L.H. Harper","year":"1967","unstructured":"Harper L.H.: A necessary condition on minimal cube numberings. J. Appl. Probab. 4(2), 397\u2013401 (1967)","journal-title":"J. Appl. Probab."},{"issue":"3","key":"36_CR10","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00224-005-1275-6","volume":"40","author":"T. Hofmeister","year":"2007","unstructured":"Hofmeister T., Schoning U., Schuler R., Watanabe O.: Randomized algorithms for 3-SAT. Theor. Comp. Syst. 40(3), 249\u2013262 (2007)","journal-title":"Theor. Comp. Syst."},{"key":"36_CR11","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: SODA \u201904: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 328\u2013328. Society for Industrial and Applied Mathematics, Philadelphia (2004)"},{"issue":"1\u20132","key":"36_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223(1\u20132), 1\u201372 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR13","unstructured":"Levin, L.: Universal\u2019nyie perebornyie zadachi (universal search problems: in russian). Prob. Peredac. Inform. (English translation in Trakhtenbrot, B.A.: A survey of russian approaches to perebor (brute-force search) algorithms. Ann. Hist. Comput. 6(4), 384\u2013400 (1984) 9(3), 265\u2013266 (1973)"},{"key":"36_CR14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"Monien B., Speckenmeyer E.: Solving satisfiability in less than 2 n steps. Discrete Appl. Math. 10, 287\u2013295 (1985)","journal-title":"Discrete Appl. Math."},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: FOCS \u201998: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p. 628. IEEE Computer Society, Washington (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"36_CR16","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chicago J. Theor. Comput. Sci. 115 (1999)"},{"issue":"3","key":"36_CR17","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi R., Pudl\u00e1k P., Saks M.E., Zane F.: An improved exponential-time algorithm for k-SAT. J. ACM 52(3), 337\u2013364 (2005)","journal-title":"J. ACM"},{"key":"36_CR18","doi-asserted-by":"crossref","unstructured":"Rolf, D.: Derandomization of PPSZ for unique k-SAT. In: Bacchus, F., Walsh, T. (eds.) SAT. Lecture Notes in Computer Science, vol. 3569, pp. 216\u2013225. Springer, Berlin (2005)","DOI":"10.1007\/11499107_16"},{"issue":"1","key":"36_CR19","doi-asserted-by":"crossref","first-page":"111","DOI":"10.3233\/SAT190005","volume":"1","author":"D. Rolf","year":"2006","unstructured":"Rolf D.: Improved bound for the PPSZ\/Sch\u00f6ning-algorithm for 3-SAT. J. Satisf. Boolean Model. Comput. (JSAT) 1(1), 111\u2013122 (2006)","journal-title":"J. Satisf. Boolean Model. Comput. (JSAT)"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: FOCS \u201999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 410. IEEE Computer Society, Washington (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"4","key":"36_CR21","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32(4), 615\u2013623 (2002)","journal-title":"Algorithmica"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0036-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-010-0036-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0036-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:52:58Z","timestamp":1740012778000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-010-0036-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,16]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["36"],"URL":"https:\/\/doi.org\/10.1007\/s11786-010-0036-3","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"type":"print","value":"1661-8270"},{"type":"electronic","value":"1661-8289"}],"subject":[],"published":{"date-parts":[[2010,4,16]]}}}