loading...
The Resolution Complexity of Random Constraint Satisfaction Problems
Cambridge, Massachusettes October 11-October 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.123820744th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Michael Molloy, Mohammad Salavatipour, "The Resolution Complexity of Random Constraint Satisfaction Problems," Foundations of Computer Science, Annual IEEE Symposium on, pp. 330, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2003.1238207,
author = {Michael Molloy and Mohammad Salavatipour},
title = {The Resolution Complexity of Random Constraint Satisfaction Problems},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2003},
issn = {0272-5428},
pages = {330},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238207},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - The Resolution Complexity of Random Constraint Satisfaction Problems
SN - 0272-5428
SP
EP
A1 - Michael Molloy,
A1 - Mohammad Salavatipour,
PY - 2003
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Michael Molloy, University of Toronto
Mohammad Salavatipour, University of Toronto
We consider random instances of constraint satisfaction problems where each variable has domain size d, and each constraint contains t restrictions on k variables. For each (d, k, t), we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.
Citation:
Michael Molloy, Mohammad Salavatipour, "The Resolution Complexity of Random Constraint Satisfaction Problems," focs, pp.330, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.