๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

No coin nor oath required. For personal study only.

โœฆ 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].


๐Ÿ“œ SIMILAR VOLUMES