{"id":12834,"date":"2021-11-22T18:24:43","date_gmt":"2021-11-22T23:24:43","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12834"},"modified":"2021-11-22T18:24:43","modified_gmt":"2021-11-22T23:24:43","slug":"tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/","title":{"rendered":"TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-96-09
\nMarch 1996<\/p>\n

A Better Upper Bound for the Unsatisfiability Threshold<\/h2>\n
\n
\n
\n
\n
\n
L. M. Kirousis, E. Kranakis, D. Krizanc<\/div>\n<\/div>\n
\n

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

Let phi be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number kappa such that if the ratio of the number of clauses over the number of variables of phi strictly exceeds kappa, then phi is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that kappa leq 5.191. This upper bound was improved by Kamath, Motwani, Palem, and Spirakis to 4.758, by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of kappa is around 4.2. In this work, we show that this upper bound can be improved to 4.667. Our proof is elementary and short, and does not use unverifiable mechanical calculations. Moreover it generalizes in a straightforward manner to k-SAT, for k>3.<\/p>\n<\/div>\n

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

Carleton University Technical Report TR-96-09 March 1996 A Better Upper Bound for the Unsatisfiability Threshold L. M. Kirousis, E. Kranakis, D. Krizanc Abstract Let phi be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number kappa such that if the ratio of the number […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12155,"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-96-09: A Better Upper Bound for the Unsatisfiability Threshold - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-09 March 1996 A Better Upper Bound for the Unsatisfiability Threshold L. M. Kirousis, E. Kranakis, D. Krizanc\" \/>\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-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/\" \/>\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-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/\",\"name\":\"TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-22T23:24:43+00:00\",\"dateModified\":\"2021-11-22T23:24:43+00:00\",\"description\":\"Carleton University Technical Report TR-96-09 March 1996 A Better Upper Bound for the Unsatisfiability Threshold L. M. Kirousis, E. Kranakis, D. Krizanc\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/#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 1996\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold\"}]},{\"@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-96-09: A Better Upper Bound for the Unsatisfiability Threshold - School of Computer Science","description":"Carleton University Technical Report TR-96-09 March 1996 A Better Upper Bound for the Unsatisfiability Threshold L. M. Kirousis, E. Kranakis, D. Krizanc","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-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/","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-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/","name":"TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-22T23:24:43+00:00","dateModified":"2021-11-22T23:24:43+00:00","description":"Carleton University Technical Report TR-96-09 March 1996 A Better Upper Bound for the Unsatisfiability Threshold L. M. Kirousis, E. Kranakis, D. Krizanc","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-09-a-better-upper-bound-for-the-unsatisfiability-threshold\/#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 1996","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/"},{"@type":"ListItem","position":5,"name":"TR-96-09: A Better Upper Bound for the Unsatisfiability Threshold"}]},{"@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\/12834"}],"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=12834"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12834\/revisions"}],"predecessor-version":[{"id":12835,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12834\/revisions\/12835"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12155"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}