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：“伽罗瓦域上低密度方检查纠错码的统计力学”欧洲物理学快报。

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 高级平均场方法”麻省理工学院出版社。

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：“分布问题上多项式时间多一与真值表可约性之间的差异”计算理论。

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)