ニューラルネットワーク（NN）の性能と活性化関数の関係にまつわる2つの研究の流れがあります．1つは，記憶容量の問題の統計力学的解析です．記憶容量とは，二値分類モデルが記憶できるランダムなデータの最大数（パラメータあたり）で，モデルの表現能力の指標の一つです．もう1つは，無限幅NNとGauss過程の関連に関するものです．この研究の流れは，NNの高い性能に対してより深い洞察を与える理論として注目されています．これらの研究は独立に発展してきましたが，両者には深いつながりがあることを指摘します．

統計力学と組合せ最適化の関連は長らく指摘されています．特に，充足可能性問題 (SAT) やグラフ彩色問題などの，離散変数の 制約充足問題 (Constraint Satisfaction Problem, 以下 CSP) に対しては，統計物理学の観点からの研究が進んでいます．一方で，連続変数 CSP に対する統計力学的な研究はあまりなされていません．本論文では，ガラスのモデルとして統計物理学で研究されている「球のパッキング」問題が，連続変数 CSP として捉えられることに着目します．球のパッキングは「ジャミング転移」と呼ばれる相転移現象を示すことが知られています．本論文では，連続変数 CSP の単純な例であるパーセプトロンの挙動を統計力学の手法を用いて解析し，球のパッキングと同様のジャミング転移が起こることを示します．

本記事では，ランダムな 3-SAT のインスタンスを解くアルゴリズムをいくつか実装して性能を比較します．そして，サーベイ伝搬法に基づいたアルゴリズムが高い性能を持つことを確認します．

K-SAT は、いくつかの変数からなる論理式を充足するような真偽値の割当を求める組合せ最適化問題です。K-SATはNP完全問題であることが示されており、現在のところ、入力サイズに対して最悪多項式時間で解くアルゴリズムの存在は知られていません。K-SAT の難しさの原因を理解し、K-SAT を平均的に高速に解くヒューリスティックを開発するための研究が進められています。本論文では、統計力学、特にスピングラス理論の手法を用いて K-SAT を解析し、上の 2 つの問いに対する洞察を与えます。