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

Let Cn,cn2,k,t 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 Cn,cn2,k,t 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].