Analyses of Randomized Algorithms for Constraint Satisfaction Problems

点击翻译按钮获取中文摘要

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.