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

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
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/9483

Title: Exponential Bounds for DPLL Below the Satisfiability Threshold
Authors: Achlioptas, D.
Beame, P.
Molloy, M.
Issue Date: 2004
Publisher: Society for Industrial and Applied Mathematics
Citation: Achlioptas, D., Beame, P., & Molloy, M. (2004). Exponential bounds for DPLL below the satisfiability threshold. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA. (pp. 132-133). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics.
Abstract: For each k ≤ 4, we give τk > 0 such that a random k-CNF formula F with n variables and ⌊rkn⌋ clauses is satisfiable with high probability, but ORDERED-DLL takes exponential time on F with uniformly positive probability. Using results of [2], this can be strengthened to a high probability result for certain natural backtracking schemes and extended to many other DPLL algorithms.
Description: Copyright (c) 2004 SIAM. All rights reserved.
URI: http://hdl.handle.net/1807/9483
ISBN: 0-89871-558-X
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
exponential bounds.pdf151.9 kBAdobe PDF
exponential bounds.pdf.txt12.22 kBText

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