Document

論文紹介 Solving NP Complete Problems Using
P Systems with Active Membranes
上田研究室 M1 原耕司
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
[email protected]
情報源

The P Systems Web Page


http://psystems.disco.unimib.it/
会議の告知、論文などが入手可能
[email protected]
P System とは





計算モデル
生体膜からヒントを得ている
階層的な膜・シンボルの多重集合・反応ルール
チューリングマシンと等価
（原理的には）指数オーダーの空間を使って
NP完全問題を多項式時間で解ける
[email protected]
例
シンボル
ルール
ルールの
優先度
アドレッシング
モード
[email protected]
[email protected]
用語

Acitve membrane

膜を分割できる仕組み
膜の番号

Elementary membrane

内部に膜を持たない膜
[email protected]
膜の特性
-,+,0
膜分割は必要

膜分割がない P system では NP 完全問題を
多項式ステップで解くことができない
(if P ≠ NP)

∵そのような P system はチューリングマシンで
多項式時間でシミュレート可能
[email protected]
LMNtal との比較

同じところ




階層的な膜構造
ルールは膜に所属する
非決定的にルールが適用される
違うところ


リンクがない
絶対時刻があり、同一ステップでは
できる限りたくさんのルールが適用される
[email protected]
SATを解くアルゴリズム

極端なデータ並列


背景：DNA計算 7 edged HPP [Adleman,1994]
全ての組みあわせを生成→評価
[email protected]
解くべき SAT の表現

SAT α がこう表されているとする
[email protected]
初期設定
扱うシンボル
出力シンボル
膜のID
膜の構造
膜0の中身
膜1の中身
[email protected]
反応ルール
真理値表を生成
カウンタ
変数束縛
充足検証
結果出力
[email protected]
日本語で説明

膜
データ構造
x=0,y=0の世界
x=0,y=1の世界
[email protected]
x=1,y=0の世界
x=1,y=1の世界
・・・
日本語で説明

膜
データ構造
x=0,y=0 → NG
x=0,y=1 → OK
[email protected]
x=1,y=0 → NG
x=1,y=1 → NG
・・・
簡単な例

SAT α = C1∧C2


C1=(￢ x1 ∨ ￢ x2
)
C2=( x1 ∨ ￢ x2 ∨ x1 )
対応

初期状態
[email protected]
生成フェーズ

全ての組み合わせを生成
[email protected]
検証フェーズ


C1=(￢ x1 ∨ ￢ x2

C2=(
)
x1 ∨ ￢ x2 ∨ x1 )
それぞれの膜で式を評価



節Cmの中で true になる項を rm に変える
Cm = true ⇔ ∃rm
SAT α = true ⇔ ∀i∈[1..m] ∃ri
x1を評価
[email protected]
x2を評価
検証フェーズ


C1=(￢ x1 ∨ ￢ x2

C2=(
x1 ∨ ￢ x2 ∨ x1 )
各節が true かどうかをチェック
カウンタ
C1をチェック
C2をチェック
[email protected]
)
計算量（ステップ数）

n + 2m + 5



n : 変数の数
m : 節の数
問題サイズに対して線形
[email protected]
問題点

空間の見積もり




仮に分子計算にマッピングすると
アボガドロ数 : 6 * 10^23 ≒ 2^61
膜 1[mol] で 60 変数程度の SAT しか解けない
実用化はまだまだ
[email protected]
まとめ


P system の紹介をした。
P system により NP 完全問題を
線形ステップで解くアルゴリズムを紹介した。
[email protected]