本研究課題では，統計力学的手法により計算限界解明の新たな道筋を開くことを大きな目標に掲げている．技術的には統計力学的手法を計算論的にどのように厳密化するか，が重要な課題である．その具体的な研究対象として，SAT 問題（とくに Max3XORSAT 問題）の解空間の構造と平均時計算困難性について，統計力学的な解析手法により予想されている描像を厳密に示すこと，また，統計力学的にも魅力的な新たな研究テーマを提供する研究を進めてきた．本年度は，昨年度に渡辺が明らかにした最尤割当解を求める Max3XORSAT 問題に対するメッセージ伝搬法の限界を，より一般的な枠組みで考える研究を進めた（森，小柴，山本，渡辺）．とくに，昨年度の C01 班キックオフワークショップで，研究協力者の Zdeborova が提案した，uniquely extensible k-CSP への拡張，メッセージ伝搬法の拡張系を考え，より一般的な結果を厳密に得ることに成功した（現在，論文執筆中）．一般の SAT 問題の計算複雑さに関する研究でも進展が得られた．まず，解空間の構造解析では，統計力学的な近似解析から得られている解空間の構造に関する予想を，一般の CNF-SAT において，部分的にではあるが厳密に証明することに，渡辺, Kane (Stanford Univ.) が成功した．山本は，牧野（A01 班），玉置（A02 班）と共同で，3SAT 問題を解く決定性の最悪時計算量としては現在世界最速のアルゴリズムを提案した．