test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works
       

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9460

Title: A sharp threshold in proof complexity yields lower bounds for satisfiability search
Authors: Molloy, M.
Beame, P.
Achlioptas, D.
Issue Date: 2004
Publisher: Elsevier
Citation: Achlioptas, D., Beame, P., & Molloy, M. (2004). A sharp threshold in proof complexity yields lower bounds for satisfiability search. Journal of Computer and System Sciences, 68(2), 238-268.
Abstract: Let F(ρn,∆n) denote a random CNF formula consisting of ρn randomly chosen 2-clauses and ∆n randomly chosen 3-clauses, for some arbitrary constants ρ,∆ ≥ 0. It is well-known that, with probability 1−o(1), ifρ > 1 then F(ρn,∆n) has a linear-size resolution refutation. We prove that, with probability 1 − o(1), if ρ < 1 then F(ρn,∆n) has no subexponential-size resolution refutation. Our result also yields the first proof that random 3-CNF formulas with densities well below the generally accepted range of the satisfiability threshold (and thus believed to be satisfiable) cause natural Davis-Putnam algorithms to take exponential time (to find a satisfying assignment).
Description: The journal version of this article can be found at: www.elsevier.com/locate/yjcss
URI: http://hdl.handle.net/1807/9460
ISSN: 0022-0000
Rights: IMPORTANT NOTICE: TO USERS OF THIS DATA ALL DATA WAS COLLECTED THROUGH THE CONSIDERABLE EFFORTS OF THE RESEARCHERS CONTRIBUTING TO IT. WHILE THE DATA CAN BE USED FOR NEW ANALYSES, Contact should be main to the collector of this data prior to publication and ACKNOWLEDGEMENT MUST BE EXPLICITLY MADE AS TO THE COLLECTOR AND CONTRIBUTOR OF THESE DATA.
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
post print - a sharp threshold.pdf299.78 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

uoft