計算の複雑さと力学系(複雑系5)
スポンサーリンク
概要
- 論文の詳細を見る
命題論理式の充足可能性問題(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この予想の検証は今後の課題である.
- 1997-08-20
著者
関連論文
- 計算の複雑さと力学系(複雑系5)
- 18pRH-8 RNNのon-line学習における到達不可能性 II
- 23pPSA-22 RNNのon-line学習における到達不可能性
- 29pWB-7 力学系によるマイクロスリップのモデル(神経回路・情報統計力学)(領域11)
- 23aPS-59 マイクロスリップの力学系モデル
- 21pTP-1 人間の選択によって進化したニューラルネットワークと触覚ディスプレイを用いたアクティブタッチの研究(生物・生態系(社会・言語・ゲーム等含む)2,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- 22pZB-2 Nonlincar Computation II
- 29a-WG-8 計算の複雑さと力学系
- κSATの解探索における臨界性と力学系的性質
- 26p-H-11 2次元セルオートマトンによる原始細胞のモデル
- 1p-YN-2 細胞の起源と自己複製
- 12aTC-7 Open-ended な生態系と keystone 種(生態系・ゲーム等, 領域 11)
- 29pPSA-56 Keystone種と生態系のネットワーク構造(領域11ポスターセッション)
- 27aWD-8 細胞の運動性の進化(生物系)(領域11)
- 27aWD-9 運動を伴う言語獲得のダイナミクス(生物系)(領域11)
- 29aWE-5 有限状態文法の複雑化のモデル研究
- 6a-YD-5 免疫ネットワークにおける特異性の進化III
- 1S18 予測行動をおこなう個体のグループゲーム
- 29a-WG-6 空間パターンを利用した生活環のモセルとそのダイナミクス
- 14aPS-23 力学系による行為の切り換えのモデル(ポスターセッション, 領域 11)
- 28aWB-1 アクティブパーセプションへの力学系アプローチ(神経系)(領域11)
- 31aPS-50 感覚運動結合系による動的知覚のモデル
- 18pRH-4 動的認識システムの相互作用のダイナミクス
- 22pZB-4 談話構造の力学系モデル
- 24aT-7 言語コミュニケーションの力学系モデル
- 1p-YN-8 数理言語によりコミュニケーションする集団のモデル
- 6a-YD-7 数理原理モデルにおけるプロトタイプ生成のダイナミクス
- 13pTK-3 身体とセンサーの相互作用モデルと運動の複雑さ(生物系, 領域 11)
- 29pPSA-55 Braitenberg's Vehicle 15号の設計とシミュレーション(領域11ポスターセッション)
- 9aTA-12 先読みプレーヤーによるゲームのダイナミクス(生物・生態系,領域11)
- 27aPS-47 動的認識システムの相互学習のダイナミクス(27aPS 領域11,領域12合同ポスターセッション,領域11(統計力学,物性基礎論,応用数学,力学,流体物理分野))
- 27aPS-45 自己複製セルオートマトンと進化(27aPS 領域11,領域12合同ポスターセッション,領域11(統計力学,物性基礎論,応用数学,力学,流体物理分野))