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

Presentation on theme: "論文紹介 - Solving NP Complete Problems Using P Systems with Active Membranes 2004/10/20(Wed)"— Presentation transcript:

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

2 出典 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,

3 情報源 The P Systems Web Page 会議の告知、論文などが入手可能
会議の告知、論文などが入手可能

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

5 例 シンボル ルール ルールの優先度 アドレッシング モード

6

7 用語 Acitve membrane Elementary membrane 膜を分割できる仕組み 内部に膜を持たない膜 膜の特性 膜の番号
-,+,0 膜の番号

8 膜分割は必要 膜分割がない P system では NP 完全問題を多項式ステップで解くことができない (if P ≠ NP)

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

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

11 解くべき SAT の表現 SAT α がこう表されているとする

12 初期設定 扱うシンボル 出力シンボル 膜のID 膜の構造 膜0の中身 膜1の中身

13 反応ルール 真理値表を生成 カウンタ 変数束縛 充足検証 結果出力

14 日本語で説明 データ構造 膜 ・・・ x=0,y=0の世界 x=1,y=0の世界 x=0,y=1の世界 x=1,y=1の世界

15 日本語で説明 データ構造 膜 ・・・ x=0,y=0 → NG x=1,y=0 → NG x=0,y=1 → OK x=1,y=1 → NG

16 簡単な例 SAT α = C1∧C2 初期状態 C1=(￢ x1 ∨ ￢ x2 ) C2=( x1 ∨ ￢ x2 ∨ x1 ) 対応

17 生成フェーズ 全ての組み合わせを生成

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

19 検証フェーズ 各節が true かどうかをチェック C1=(￢ x1 ∨ ￢ x2 ) C2=( x1 ∨ ￢ x2 ∨ x1 ) カウンタ

20 計算量（ステップ数） n + 2m + 5 問題サイズに対して線形 n : 変数の数 m : 節の数

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

22 まとめ P system の紹介をした。 P system により NP 完全問題を 線形ステップで解くアルゴリズムを紹介した。