loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
ASCII Text
x 
 
Harold Connamacher, Michael Molloy, "The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem," Foundations of Computer Science, IEEE Annual Symposium on, pp. 590-599, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.66,
author = {Harold Connamacher and Michael Molloy},
title = {The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {590-599},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.66},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem
SN - 0272-5428
SP590
EP599
A1 - Harold Connamacher,
A1 - Michael Molloy,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Harold Connamacher, University of Toronto
Michael Molloy, University of Toronto
We determine the exact threshold of satisfiability for random instances of a particular NP-hard constraint satisfaction problem. The problem appears to share many of the threshold characteristics of random k-SAT for k ≥ 3; for example, we prove the problem almost surely has high resolution complexity.We also prove the analogue of the (2 + p)-SAT conjecture for a class of problems that includes this problem and XOR-SAT.
Citation:
Harold Connamacher, Michael Molloy, "The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem," focs, pp.590-599, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.