Characterization of resolution complexity of general random constraint satisfaction problem

M.Phil.We consider a random model of General Constraint Satisfaction Problems (CSPs) in which variables are over a finite domain (of size d) and each constraint has the same arity k. Each constraint has a type specifying the restrictions on its k variables. A restriction on k variables is a combination of values they could not jointly take. For fixed d; k, a constraint type distribution P is a distribution on the set of all possible constraint types.Given constraint distribution P and constraint realization probability p, we denote by CSPₙ;ₚ(P) a n-variable random instance constructed as follows: independently for each k-variable set, with probability p add a constraint over the k variables to the instance, whose type is sampled from P. We focus on the regime when p = c(k - 1)!/nᵏ⁻¹, where c is a constant. We think of P as fixed and c a controlling parameter, and study the behavior of the random instance when n goes to infinity. We define a variant of the Galton-Watson branching process, which is parameterized by P and c, such that it approximates local subinstances in CSPₙ;cₙ⁻(ᵏ⁻¹) (P) when n is large. We study a special event in the branching process which corresponds to containment of a small and sparse unsatisfiable subinstance in CSPₙ;cₙ⁻(ᵏ⁻¹) (P). Given P belonging to a certain family of constraint distributions, there is a finite threshold value c* to the parameter c, at which the probability for the property to hold in the branching process turns from zero to positive.We conjecture that for all c > c*, CSPₙ,ₚ(P) has polylogarithmic resolution complexity almost surely, and for all c c*.我們考慮一個廣義約束滿足問題(General Constraint Satisfaction Problem, General CSP)的隨機模型，族內問題的變數可從大小為d的有限定義域取值，每項約束均為k元。每項約束屬一類型，其類型指定該約束之k變數所受(可多於一項)的限制。每項限制為該k變數不可同時取值的組合。對於固定的d; k，約束概率分佈P為所有d值k元的約束類型集上的分佈。給定約束概率分佈P，約束實現概率p，我們以CSPₙ;ₚ(P)表示共有n變數、按以下方法構成的隨機約束滿足問題：獨立對於每個k變數組合，以概率p將它實現為問題中的一項約束，約束類型根據P隨機選出。我們專注於參數區域p = c(k - 1)!/nᵏ⁻¹，c為獨立於n的常數。我們考慮P為一固定分布，c為模型控制參數，並研究變數量n趨近無窮大時此隨機問題的行為。我們定義一Galton-Watson分支過程(Galton-Watson branching process)的變種，其參數為P和c，可用以模仿n足夠大時CSPₙ;ₚ(P)中的局部子問題。我們研究這類分支過程可出現的一種特殊事件，該事件對應CSPₙ;ₚ(P)包含了小且條件量疏的不可滿足子問題。當P屬於某特殊約束概率分佈族時，參數c將有一使分支過程滿足該屬性的概率由零轉為正的有限臨界值c*。我們猜想c > c*時，CSPₙ;ₚ(P)的歸結複雜度(resolution complexity)近乎必然為O(polylog(n))，而c c*時的歸結複雜度上限。Cham, Hiu Sze.Thesis M.Phil. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 55-56).Abstracts also in Chinese.Title from PDF title page (viewed on 09, February, 2021)