Resolution Complexity of Random Constraint Satisfaction Problems

The resolution complexity of random constraint satisfaction problems is a widely studied topic. This line of research started with a seminal paper by Chvátal and Szemeréd. They showed that for any 𝑘 ≥ 3, w.h.p. an unsatisfiable random 𝑘-SAT instance has exponentially high resolution complexity when the clause density is a constant. The result was later extended to settings with super-constant clause density. The random (𝑑, 𝑘, 𝑡)-CSP model is another well-studied random CSP model. It is a natural generalization of the random 𝑘-SAT model by allowing a more general domain of 𝑑 ≥ 2 variable values instead of {TRUE, FALSE}, and allowing 𝑡 ≥ 1 restrictions in each constraint (clause) instead of only one. Earlier results give the whole picture for the resolution complexity of random (𝑑, 𝑘, 𝑡)-CSP instances for every constant triple of (𝑑, 𝑘, 𝑡) and every constant constraint density Δ. However, very little is known for the resolution complexity when the constraint density grows beyond constant. In this thesis, we generalize the resolution complexity results for random (𝑑, 𝑘, 𝑡)-CSP to settings with super-constant constraint density, just like the later studies extended the 𝑘-SAT result of Chvátal and Szemeréd to settings with super-constant clause density. We introduce a general approach for studying the resolution and tree resolution complexity of random (𝑑, 𝑘, 𝑡)-CSP with super-constant constraint density. We are particularly interested in the ranges of constraint density where the resolution and tree resolution complexity drop from superpolynomial to polynomial. By applying our approach, we obtain new lower and upper bounds on these constraint density ranges. In particular, the bounds for the tree resolution complexity are tight up to a 𝑜(1) term in the exponent. The settings we consider include two generalizations of the random 𝑘-SAT model, and the bounds we obtain almost match the best known bounds for the random 𝑘-SAT model. Therefore, our results can be regarded as generalizations of the resolution complexity results for random 𝑘-SAT. Finally, it seems possible to apply our approach to other models of random CSPs as well.

Department dc:contributor.department

Computer Science

Year dc:date.issued

2016

Author dc:creator

• Yung, Chun Kong

Advisor dc:contributor.advisor

• Molloy, Michael

• Proof Complexity
• Random CSP
• Resolution

Handle dc:identifier.uri

http://hdl.handle.net/1807/73210

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/73210