Document

計算可能性
計算可能性の理論
可解(solvable)
問題Aを解くアルゴリズムが存在するとき、
Aは可解であるという。
非可解(unsolvable)
問題Aを解くアルゴリズムが存在しないとき、
Aは非可解であるという。
1
非可解
プログラムの停止問題は非可解
入力：プログラムP、データx
出力：計算が有限ステップで停止するならば Yes,
そうでなければ No
計算可能性
計算可能性の理論
可解(solvable)
問題Aを解くアルゴリズムが存在するとき、
Aは可解であるという。
非可解(unsolvable)
問題Aを解くアルゴリズムが存在しないとき、
Aは非可解であるという。
3
複雑さのクラスP
クラスP
多項式時間で解ける問題のクラス
例
•
•
•
•
•
ソート
グラフの最短経路
平面グラフの判定
最小木
...
4
計算量
多項式オーダー
ある定数kを用いて、O(nk)で書けるという意味である。
線形オーダー
O(n)と書けるという意味である。
5
計算の複雑さ
なぜ、多項式時間か？
データがｎ個の問題を解くのに2種類のアルゴリズムがある。
アルゴリズムAは2n回の演算を用いて問題を解く
アルゴリズムBが1000n5回の演算を用いて問題を解く
もし、1秒に1億回の演算をする計算機を使うと、
この問題を解くのにかかる時間は
データ
A
B
10
20
30
40
50
60
70
80
90
10万分の1秒 100分の1秒 11秒 3時間 130日 371年 37万年 4億年４千億年
1秒
32秒
4分
17分
52分 2時間 5時間
9時間 16時間
6
決定性計算
deterministic computation
start
停止
7
非決定性計算
nondeterministic computation
start
選択
停止
8
複雑さのクラスNP
nondeterministic polynomial
クラスNP
決定問題Aに対し、非決定性アルゴリズムが存在して、
規模nの問題例について、それがyesの解をもつ
場合にはnの多項式オーダー長でyesを与えるものが
少なくとも一つ存在するならば AはクラスNPに属する.
例
•
•
•
•
３SAT問題
最大独立点集合問題
ハミルトン閉路
...
9
複雑さのクラスPとNP
簡単
クラスP
多項式時間で解けば
クラスNP
例挙された解が条件を満たすかどうかの判定が
多項式時間で可能でありさえすれば
10
複雑さのクラスPとNP
簡単
最小全域木問題
クラスP
多項式時間で解けば
クラスNP
例挙された解が条件を満たすかどうかの判定が
多項式時間で可能でありさえすれば
11
Satisfiability Problem(SAT)
SAT
リテラルx1 , x1 , x2 , x2 , … , xn , xn から作られたリテラルの和の節
C1,C2, …,Cmが与えられたとき、全ての節を１にするような変数へ
の0,1の割り当てがあるかどうか判定せよ。
例
例
C1 = x1 + x2 + x3
C2 = x2 + x3
C3 = x3 + x4
C1 = x1
C2 = x1
x1=1, x2=0, x3=0, x4=1
x1=1
x1=0
C1 =1
C2 =1
C3 =1
C1 =1, C2 =0
C1 =0, C2 =1
12
複雑さのクラスPとNP
簡単
クラスP
SAT問題
多項式時間で解けば
クラスNP
例挙された解が条件を満たすかどうかの判定が
多項式時間で可能でありさえすれば
13
問題間の帰着
問題Aの任意の問題例Xに対し、問題Bの問題例ｆ（X)を
構成でき、AにおけるXの答（yesあるいはno)とBにおける
ｆ（X)の答が一致するとき、AはBに帰着可能である。
ただし、ｆは多項式時間で計算できる場合には、
多項式的に帰着可能という。
14
NP困難とNP完全（P50,93,138）
クラスNPの任意の問題Aがある問題Bに多項式的に帰着
可能であれば、BはNP困難(NP-hard)であるという。
さらに、このB自身がNPに属していれば、
BはNP完全(NP-complete)であるという。
15
未解決問題：P=NP ?
もしNP完全に属する問題の一つが、多項式時間で解けたら、
クラスNPに属する問題は全て多項式時間で解ける。
即ち、P=NP。
NP
1971年以来世界中の研究者がトライしても、
未解決なので、P=NPだと予想されている。
NP完全
P
16
NP完全問題の例
現在、数千（もしくは、さらに多くの）NP完全問題が
知られている。
例
SAT
３SAT
Clique
Vertex-cover
Vertex-coloring
Edge-coloring
Subset-sum
17
Satisfiability Problem(SAT)
最初にNP完全であることが証明された問題
S.A. Cook 1971年
SAT
リテラルx1 , x1 , x2 , x2 , … , xn , xn から作られたリテラルの和の節
C1,C2, …,Cmが与えられたとき、全ての節を１にするような変数へ
の0,1の割り当てがあるかどうか判定せよ。
例
例
C1 = x1 + x2 + x3
C2 = x2 + x3
C3 = x3 + x4
C1 = x1
C2 = x1
x1=1, x2=0, x3=0, x4=1
x1=1
x1=0
C1 =1
C2 =1
C3 =1
C1 =1, C2 =0
C1 =0, C2 =1
18
NP完全の証明
知られたNP完全の問題
多項式時間の帰着
証明したい問題
19
NP完全の証明
演習問題1
Clique 問題がNP完全であることを証明せよ。
Clique問題
グラフが与えられたとき、サイズkのclique（完全部分グラフ）を
持つかどうか判定せよ。
演習問題1
NP完全の証明
Clique 問題がNP完全であることを証明せよ。
証明：
Clique問題がNPに属するのは自明です。
演習問題1
N P 完全の証明
Clique 問題がNP完全であることを証明せよ。
証明：
Clique問題がNPに属するのは自明です。
3SAT問題がClique問題に多項式時間帰着可能であること
を示せばいい。
知られたNP完全の問題
3SAT問題
多項式時間の帰着
証明したい問題
Clique問題
N P 完全の証明
3SATのインスタンス
例
Clique問題
サイズ3のclique?
C1 = x1 + x2 + x3
C2 = x1 + x2 + x3
C3 = x2 + x3 + x4
x1
x1
x2
x2
x3
x3
=1, xx22=1,
=0, xx33=0,
=0, xx44=*
=1
xx11=*,
C1 =1
C2 =1
C3 =1
Yes
x2
x3
Yes
x4
Q.E.D
演習問題2
NP完全の証明
ハミルトングラフ問題がNP完全であることを証明せよ。
グラフGにすべての点を通る閉路Zがあるとき、Gはハミ
ルトングラフ（Hamiltonian graph)といい、Zをハミルト
ン閉路という。
出発点
24
N P 完全の証明
演習問題2
ハミルトングラフ問題がNP完全であることを証明せよ。
証明：
ハミルトングラフ問題がNPに属するのは自明です。
3SAT問題がハミルトングラフ問題に多項式時間帰着可能である
ことを示せばいい。
知られたNP完全の問題
3SAT問題
多項式時間の帰着
証明したい問題
ハミルトングラフ
問題
N P 完全の証明
部品
例
B
A
x1
x2
C1 = x1 + x2 + x3
C2 = x1 + x2 + x3
C3 = x1 + x2 + x3
x3
N P 完全の証明
部品
例
B
A
x1
ハミルトン閉路
x2
C1 = x1 + x2 + x3
C2 = x1 + x2 + x3
C3 = x1 + x2 + x3
x3
x1 =1
x2 =1
x3 =1
Q.E.D

Download Report