Analyses of Randomized Algorithms for Constraint Satisfaction Problems

约束满足问题的随机算法分析

• 批准号: 13680400
• 负责人: WATANABE Osamu
• 金额: $ 2.11万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680400/
• 关键词: Probabilistic Algorithms; Randomized Algorithm; Belief Propagation; Constraint Satisfaction Problem; Low-Density Parity Check; Average-Case Analysis of Algorism; 疎行列パリティ検査符号; Belief Propagation法; 統計力学的手法

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.

我们为各种约束满意度问题分析了几种随机 /概率的算法。对于具体的问题，我们选择了（1）低密度奇偶校验检查代码（LDPCCD）的解码问题，以及（2）搜索简单逻辑公式的满足分配的问题（SAT）。对于LDPCCD，我们分析了（a）一种概率算法，所谓的信念传播，以及（b）随机的局部搜索算法。对于这两种算法，我们获得了一些统计搜索算法。基于我们的分析，我们可以提出一种改进的本地搜索算法。我们还获得了一些（主要是两个）理论结果，这些结果一般而言。当我们知道解决方案是唯一的时，第一个是问题的硬度。我们给了硬度的复杂性理论表征。第二个是SAT的平均案例完整性；我们表明，当更改输入分布甚至巧妙地改变输入分布时，我们都会有所不同。

项目成果

Y.Kabashima, D.Saad: "The TAP Approach to Intensive and Extensive Connectivity Systems"Advanced Mean Field Methods (MIT Press). 51-66 (2002)

Y.Kabashima、D.Saad：“密集和广泛连接系统的 TAP 方法”高级平均场方法（麻省理工学院出版社）。

K. Nakamura, Y. Kabashima, and D. Saad: "Statistical Mechanics of Low-Density Party Check Error Correcting Codes over Galois Field"Europhysics Letters. 56. 610-616 (2001)

K. Nakamura、Y. Kabashima 和 D. Saad：“伽罗瓦域上低密度方检查纠错码的统计力学”欧洲物理学快报。

S. Aida, R. Sculer, T. Tsukiji and O. Watanabe: "The Difference between polynominal-time many-one and truth-table reducibilities on distributional problems"Theory of Comput. Systems. 35. 449-463

S. Aida、R. Sculer、T. Tsukiji 和 O. Watanabe：“分布问题上多项式时间多一与真值表可约性之间的差异”计算理论。

D.Saad, Y.Kabashima, R.Vicent: "TAP For Parity Check Error Correcting Codes Advanced Mean Field Methods"MIT Press. 67-84 (2001)

D.Saad、Y.Kabashima、R.Vicent：“奇偶校验纠错码的 TAP 高级平均场方法”麻省理工学院出版社。

Y.Kabashima, K.Nakamura, J.van Mourik: "Statistical mechanics of typical set decoding"Physical Review E. 66. 036125(1)-036125(6) (2002)

Y.Kabashima、K.Nakamura、J.van Mourik：“典型集合解码的统计力学”Physical Review E. 66. 036125(1)-036125(6) (2002)