計算の複雑さと力学系(複雑系5)

Abstract

命題論理式の充足可能性問題(Satisfiability problem,以下SATと表記する.)は数理論理学を背景に持つ代表的なNP完全問題であり,計算の複雑さの理論においては「実際的計算可能性」を考える上で重要な研究対象になっている.近年,このSATは数値計算を用いる実験数学的な手法によって研究されており,計算の複雑さの現実的な性質が明らかになっている.本論文では力学系の理論に基づき計算理論に新たな視点を導入する.SATのうちで,節に含まれるリテラルの数がk個である和積標準型の論理式(kCNF)の充足可能性を判定する問題を特にkSATという.本稿では主にこのkSATを取り上げる.kSATは与えられたkCNFを満たす解が存在するかどうかを判定する決定問題であり,k=1,2のときは多項式時間で解ける問題クラス(class P),k≥3のときは多項式時間では解けないと予想されている問題クラス(class NP)に属することが知られている.先行研究によると,計算コストのかかる問題の分布は一様なものではないことが示唆される.この分布の幾何学的側面を考察するために,ここではkCNFをk次元の単位区間内にコードし,充足可能式をプロットするという方法をとった.このとき3CNFの充足可能式の集合は3次元の単位立方体内部に,2CNFの充足可能式の集合はその原点を通る平面での切断面に埋め込まれることになる.結果として,このkCNFの充足可能式の集合は,k=2のとき完全な自己相似集合(フラクタル),k≥3のとき部分自己相似集合(準フラクタル)となると予想された.自己相似集合は単純な入れ子構造をもつ縮小写像系,部分自己相似集合は互いに他に含まれるような入れ子構造をもつ縮小写像系で表現される.したがってここでは,このような縮小写像系の再構成が重要な意味を持つ.k=2の場合,充足可能式の集合を縮小写像系で再構成することができたが,k≥3の場合は再構成が困難だった.このためBox-counting法で数値的にHausdorff次元を求めたところ,k=2の場合は理論値に良く一致したが,k≥3の場合は(自己相似集合を仮定した場合の)理論値からややずれるという結果を得た.3SATがclass NPに属するのは何故かという論点に戻ると,相互に他に含まれる入れ子構造をもつ縮小写像系によって生成される準フラクタルの性質により,NPの言語を認識することのできる離散力学系(アルゴリズム)において初期入力が不変集合に到達する時間(計算時間)が単純な入れ子構造をもつ縮小写像系によって生成されるPのそれよりも長くなるという説明がつく.以上を考察して,以下の予想を得た.class P ⇔ Self similar set class NP ⇔ Partially self similar setこの予想の検証は今後の課題である.