1 ELC Web 2 検証と求解パズルはなぜ面白い SUDOKU 図図 -1 数独の問題図と解答図 ( より ) 6 2 P!NP 2 1 情報処理 Vol.54 No.4 Apr

Size: px

Start display at page:

Download "1 ELC Web 2 検証と求解パズルはなぜ面白い SUDOKU 図図 -1 数独の問題図と解答図 ( より ) 6 2 P!NP 2 1 情報処理 Vol.54 No.4 Apr"

ゆりなこのえ
5 years ago
Views:

1 基応専般解説徳山豪東北大学情報科学研究科計算下界の解明の目的人間の思考と計算機の役割 cogito ergo sum SF 情報社会の前進への意義 NP 1 P!NP 2 NP 1 2 Nondeterministic Polynoimal 374 情報処理 Vol.54 No.4 Apr. 2013

2 1 ELC Web 2 検証と求解パズルはなぜ面白い SUDOKU 図図 -1 数独の問題図と解答図 ( より ) 6 2 P!NP 2 1 情報処理 Vol.54 No.4 Apr

解ける問題と解けそうな問題 1875 1960 3 18 1 2 3 4 15 5 6 36 2 2 図 -2 7 1 0 図 -2 ケーニヒスベルグの橋渡り ( 左図 ) と対応するグラフ

3 解ける問題と解けそうな問題図図 -2 ケーニヒスベルグの橋渡り ( 左図 ) と対応するグラフ ( 右図 ) 図 -3 正 12 面体のグラフ ( 左図 ) とその頂点巡礼 ( 右図 ) 5 G 1 12 図情報処理 Vol.54 No.4 Apr. 2013

4 計算階層と計算モデル図パズル : 左図を右図に駒をスライドして直す P!NP 図 P!NP P=NP NP 多項式時間計算 : 取扱い可能な有限 YES 10 4 情報処理 Vol.54 No.4 Apr

5 n n f n O f n complexity 5 f n n, n 2, n n 2 n3 定義 1 5 g n =O f n c n 0 g n <c f n n$n 0 g n =o f n c n g n <c f n g n o f n g n =W n n n 3 2 n 10 1,000 1, ,000 1,000, ,000 1,000,000, ,000 1,000,000,000, ,000 1,000,000,000,000,000,000, ,000,000 1,000,000,000,000,000,000,000,000,000,000 表 -1 計算時間と指数爆発 tractable intractable 表 -1 n=10 n 3 2 n 1000 n=70 n 3 2 n = n O n 100 O n 3 n 情報処理 Vol.54 No.4 Apr. 2013

6 休憩 : ノーベル賞の話題から ips 24 n 2 n n= n n+1 O n 階層定理 P EXP 2 2 定理 1 P EXP 2 ℵ 0 ℵ 1 ℵ 1 =2 ℵ0 ℵ 0 ℵ 1 6 EXP P 定理 2( 階層定理 ) f n >n o f n O f n log f n 2 o f n O n 3 o n 2 2 P EXP f n =n log n P EXP P EXP NP 問題の定義とその位置 6 情報処理 Vol.54 No.4 Apr

7 Yes, No Yes Yes NP NP Yes Yes 7 NP No NP NP Yes NP conp conp No Yes NP conp NP conp P3NP+coNP 7 Pratt 図 -5 階層定理 ( 左図 ) と, 検証モデルによる階層化 ( 右図 ) f n 2 f n NP EXP NP P P3NP 3EXP 図 -5 積み木倒しのシナリオ (1):NP の内部 NP 定義 2 A B f A n X B f n Y A X Yes B Y Yes 系 1 A B B P A P 情報処理 Vol.54 No.4 Apr. 2013

8 8 P 2 P 1 NP 1 図 -6 NP 完全問題の位置の可能性定義 3 A NP NP X A A NP NP A NP P=NP NP NP NP NP SAT Cook S. Cook R. Karp NP 4 NP 1 NP P NP NP 9 P=NP NP NP NP 観察 1 NP P NP 図 -6 NP P=NP NP conp P P NP N n=log N N N P 10 NP NP 8 9 n 2 #n 2 NP 情報処理 Vol.54 No.4 Apr

NP の上に積み重なる階層 P!NP 1 P NP NP より難しそうな問題 1 NP 11 1 1 1 図 -7 5 手詰め詰将棋の論理 ( 詰将棋図式は http://www.geocities. co.jp/playtown/6157/3-5te/gotedume.

9 NP の上に積み重なる階層 P!NP 1 P NP NP より難しそうな問題 1 NP 図 -7 5 手詰め詰将棋の論理 ( 詰将棋図式は co.jp/playtown/6157/3-5te/gotedume.html より引用 ) NP 積み木倒しのシナリオ (2):NP から組み上げる x y 12 x $x y "y $x 1 "y 1 $x 2 "y 2 $x 3 Q x 1, y 1, x 2, y 2, x 3, s, Checkmate 5 図 -7 x i y i Q s 5 x 1 " x 1 $ y 1 " x 2 $ y 2 " x 3 J Q x 1, y 1, x 2, y 2, x 3, s, Checkmate JQ " $ NP Yes Q x $x, Q x, E A 382 情報処理 Vol.54 No.4 Apr. 2013

10 No x Q "x, JQ x $ " 1 s 1 $x 1 Q x 1, s, Checkmate "x 1 JQ x 1, s, Checkmate conp NP " $ NP 1 "$ $" Yes "x$yq x,y No $x"yjq x,y Yes x y x y 1 p 2 $" "$ p 2 NP conp 2 "$" $"$ p 3 p k, p k, k 1 p k, k 1 p k PH P=NP p k = p k =P PH= P P P! NP PH の行き着く先 p PH k k k $, ",..., $, " k O O n +O n =O n f n f n # f nz1 +n f n =O n f nz1 =O nz1 f n = O nz1 +n=o n +O n =O n O n O n n O n 2 O k k PSPACE #9 n#n p 5 2n+1 PSPACE PSPACE PH PH k 1 P=NP P=PH PSPACE P=PSPACE 図 -8 PSPACE NP P!PSPACE P!NP n 1, 2, 13 PSPACE PSPACE 情報処理 Vol.54 No.4 Apr

11 図 -8 多項式時間階層 PH の構造 P!PSPACE 参考文献 1 Sipser, M ELC Web u.ac.jp/elc/ , Garey, M. R. and Johnson, D. S. : Computers and Intrac tability A Guide to the Theory of NP Completeness Agrawal, M., Kayal, N. and Saxena, N. : PRIMES is in P, Annals of Mathematics 160 2, pp : 次回予告徳山豪 tokuyama@dais.is.tohoku.ac.jp IBM 情報処理 Vol.54 No.4 Apr. 2013

1 ELC Web 2 検証と求解 パズルはなぜ面白い SUDOKU 図 図 -1 数独の問題図と解答図 ( より ) 6 2 P!NP 2 1 情報処理 Vol.54 No.4 Apr

1 ELC Web 2 検証と求解パズルはなぜ面白い SUDOKU 図図 -1 数独の問題図と解答図 ( より ) 6 2 P!NP 2 1 情報処理 Vol.54 No.4 Apr