{"id":12810,"date":"2021-11-21T17:12:23","date_gmt":"2021-11-21T22:12:23","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12810"},"modified":"2021-11-21T17:12:23","modified_gmt":"2021-11-21T22:12:23","slug":"tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/","title":{"rendered":"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-26
\nDecember 1995<\/p>\n

Approximating the Unsatisfiability Threshold of Random Formulas<\/h2>\n
\n
\n
\n
\n
\n
Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n
\n

Let \u001e\u0398 be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number \u0014 such that if the ratio of the number of clauses over the number of variables of \u0398\u001e strictly exceeds k\u0014, then \u0398\u001e is almost certainly unsatis\fable. By a well known and more or less straightforward argument, it can be shown that \u0014 \u0014k \u2264 5.191. This upper bound was improved by Kamath, Motwani, Palem, and Spirakis to 4.758, by \frst providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of \u0014k is around 4.2. In this work, we de\fne, in terms of the random formula \u0398\u001e, a decreasing sequence of random variables such that if the expected value of any one of them converges to zero, then \u001e\u0398 is almost certainly unsatis\fable. By letting the expected value of the \ffirst term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k\u0014 equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.598. In general, by letting the expected value of further terms of this sequence converge to zero, one can, if the calculations are performed, obtain even better approximations to \u0014k. This technique generalizes in a straightforward manner to k-SAT, for k > 3.<\/p>\n<\/div>\n

TR-95-26.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-26 December 1995 Approximating the Unsatisfiability Threshold of Random Formulas Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc Abstract Let \u001e\u0398 be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number \u0014 such that if the ratio of the number of […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-26 December 1995 Approximating the Unsatisfiability Threshold of Random Formulas Lefteris M. Kirousis,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/\",\"name\":\"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-21T22:12:23+00:00\",\"dateModified\":\"2021-11-21T22:12:23+00:00\",\"description\":\"Carleton University Technical Report TR-95-26 December 1995 Approximating the Unsatisfiability Threshold of Random Formulas Lefteris M. Kirousis,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas - School of Computer Science","description":"Carleton University Technical Report TR-95-26 December 1995 Approximating the Unsatisfiability Threshold of Random Formulas Lefteris M. Kirousis,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/","name":"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-21T22:12:23+00:00","dateModified":"2021-11-21T22:12:23+00:00","description":"Carleton University Technical Report TR-95-26 December 1995 Approximating the Unsatisfiability Threshold of Random Formulas Lefteris M. Kirousis,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-26-approximating-the-unsatisfiability-threshold-of-random-formulas\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-26: Approximating the Unsatisfiability Threshold of Random Formulas"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12810"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12810"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12810\/revisions"}],"predecessor-version":[{"id":12811,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12810\/revisions\/12811"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12810"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}