Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

✍ Scribed by Yong Gao; Joseph Culberson

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 97 KB
• Volume: 16
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(04)00460-3

✦ Synopsis

Let C 2,k,t n,cn be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish upper bounds for the tightness threshold for C 2,k,t n,cn to have an exponential resolution complexity. The upper bounds partly answers the open problems regarding the CSP resolution complexity with the tightness between the existing upper and lower bound [1].