論文紹介 - Solving NP Complete Problems Using P Systems with Active Membranes 2004/10/20(Wed)

出典 C. Zandron, C. Ferretti, G. Mauri, Solving NP-complete problems using P systems with active membranes. In Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, eds.), Springer-Verlag, London, 2000, 289--301. http://citeseer.ist.psu.edu/zandron00solving.html hara@ueda.info.waseda.ac.jp

情報源 The P Systems Web Page 会議の告知、論文などが入手可能 http://psystems.disco.unimib.it/ 会議の告知、論文などが入手可能 hara@ueda.info.waseda.ac.jp

P System とは 計算モデル 生体膜からヒントを得ている 階層的な膜・シンボルの多重集合・反応ルール チューリングマシンと等価 （原理的には）指数オーダーの空間を使って NP完全問題を多項式時間で解ける hara@ueda.info.waseda.ac.jp

例 シンボル ルール ルールの優先度 アドレッシング モード hara@ueda.info.waseda.ac.jp

hara@ueda.info.waseda.ac.jp

用語 Acitve membrane Elementary membrane 膜を分割できる仕組み 内部に膜を持たない膜 膜の特性 膜の番号 -,+,0 膜の番号 hara@ueda.info.waseda.ac.jp

膜分割は必要 膜分割がない P system では NP 完全問題を多項式ステップで解くことができない (if P ≠ NP) hara@ueda.info.waseda.ac.jp

LMNtal との比較 同じところ 違うところ 階層的な膜構造 ルールは膜に所属する 非決定的にルールが適用される リンクがない 絶対時刻があり、同一ステップでは できる限りたくさんのルールが適用される hara@ueda.info.waseda.ac.jp

SATを解くアルゴリズム 極端なデータ並列 全ての組みあわせを生成→評価 背景：DNA計算 7 edged HPP [Adleman,1994] 全ての組みあわせを生成→評価 hara@ueda.info.waseda.ac.jp

解くべき SAT の表現 SAT α がこう表されているとする hara@ueda.info.waseda.ac.jp

初期設定 扱うシンボル 出力シンボル 膜のID 膜の構造 膜0の中身 膜1の中身 hara@ueda.info.waseda.ac.jp

反応ルール 真理値表を生成 カウンタ 変数束縛 充足検証 結果出力 hara@ueda.info.waseda.ac.jp

日本語で説明 データ構造 膜 ・・・ x=0,y=0の世界 x=1,y=0の世界 x=0,y=1の世界 x=1,y=1の世界 hara@ueda.info.waseda.ac.jp

日本語で説明 データ構造 膜 ・・・ x=0,y=0 → NG x=1,y=0 → NG x=0,y=1 → OK x=1,y=1 → NG hara@ueda.info.waseda.ac.jp

簡単な例 SAT α = C1∧C2 初期状態 C1=(￢ x1 ∨ ￢ x2 ) C2=( x1 ∨ ￢ x2 ∨ x1 ) 対応 hara@ueda.info.waseda.ac.jp

生成フェーズ 全ての組み合わせを生成 hara@ueda.info.waseda.ac.jp

検証フェーズ それぞれの膜で式を評価 節Cmの中で true になる項を rm に変える Cm = true ⇔ ∃rm C1=(￢ x1 ∨ ￢ x2 ) C2=( x1 ∨ ￢ x2 ∨ x1 ) それぞれの膜で式を評価 節Cmの中で true になる項を rm に変える Cm = true ⇔ ∃rm SAT α = true ⇔ ∀i∈[1..m] ∃ri x1を評価 x2を評価 hara@ueda.info.waseda.ac.jp

検証フェーズ 各節が true かどうかをチェック C1=(￢ x1 ∨ ￢ x2 ) C2=( x1 ∨ ￢ x2 ∨ x1 ) カウンタ hara@ueda.info.waseda.ac.jp

計算量（ステップ数） n + 2m + 5 問題サイズに対して線形 n : 変数の数 m : 節の数 hara@ueda.info.waseda.ac.jp

問題点 空間の見積もり 実用化はまだまだ 仮に分子計算にマッピングすると アボガドロ数 : 6 * 10^23 ≒ 2^61 膜 1[mol] で 60 変数程度の SAT しか解けない 実用化はまだまだ hara@ueda.info.waseda.ac.jp

まとめ P system の紹介をした。 P system により NP 完全問題を 線形ステップで解くアルゴリズムを紹介した。 hara@ueda.info.waseda.ac.jp