Analyses of Randomized Algorithms for Constraint Satisfaction Problems

针对不同的约束满足问题，分析了几种随机/概率算法。对于具体问题，我们选择了(1)低密度奇偶校验码的解码问题（LDPCCD）和(2)寻找一个令人满意的简单逻辑公式分配问题（SAT）。对于LDPCCD，我们分析了(a)一种称为信念传播的概率算法，以及(b)一种随机局部搜索算法。对于这两种算法，我们都得到了一些统计搜索算法；基于我们的分析，我们可以提出一种改进的局部搜索算法。我们也得到了一些（主要是两个）关于一般约束满足问题的硬度的理论结果。第一个是当我们知道解是唯一的时候问题的难度；对硬度进行了复杂性理论表征。二是关于SAT的平均情况完备性；我们表明，即使稍微改变输入分布，补全性概念也会有所不同。

We analyzed several randomized / probablistic algorithms for various constraint satisfaction problems.For concrete problems, we chose (1) the decoding problem for low-density parity check codes (LDPCCD), and (2) the problem of searching a satisfying assignment of simple logical formulas (SAT). For LDPCCD, we analyzed (a) a probabilistic algorithm, so called belief propagation, and (b) a randomized local search algorithm. For both algorithms, we obtained some statistical search algorithm ; based on our analysis, we could propose an improve local search algorithm.We also obtained some (mainly two) theoretical results on the hardness of constraint satisfaction problems in general. The first one is on the hardness of problems when we know that the solution is unique ; we gave complexity theoretic characterization to the hardness. The second one is on the average-case completeness of SAT ; we showed that complenteness notions differ when changing input distribution even sligtly.