アルゴリズム入門（7）

(1)

宮崎修一

京都大学学術情報メディアセンター

アルゴリズム入門（ 7 ）

（問題の複雑さ）

(2)

2

ある問題が、「これだけの計算量で解ける」というのを示すのは、

比較的簡単。（実際にアルゴリズムを設計すれば良い。）

ある問題が、「これだけの計算量では解けない」ことを示すのは、

難しい。（「どんなアルゴリズムでも駄目だ」ということを証明する必要がある。）

問題の難しさ

今の所、問題の難しさを示す研究は、成功していない。

↓

問題の難しさを示すために、「ある問題が難しいとすると、

この問題も難しい」という論法が使われている。

(3)

3

Ａ：既に難しいことが分かっている問題。

Ｂ：難しいことを示したい問題。

問題の難しさを示す手法（還元、リダクション）

問題Ａ問題Ｂ

還元

問題Ａを問題Ｂに変換している（ただし、答が保存されるように）

つまり、Ｂを解くことにより、Ａを解くことが出来る。

(4)

4

i

具体例

Ａ：論理式の充足可能性問題（ＳＡＴ）難しいことが分かっている。

Ｂ：最小頂点被覆問題（ＶＣ）難しいことを示したい。

ＳＡＴ

入力：和積形論理式

f = (x

₁

+x

₂

+x

₃

) (x

₁

+x

₈

) … (x

₃

+x

₆

+x

₇

+x

₁₂

)

出力：

x , x , …, x

に

0/1

を割り当てて、

f =1

と出来るか？

YES/NO?

x

：

1 2 n

i

x

_i の否定

x

_i

=1

ならば

x =0

x

i

=1 x

_i

=0

ならば

(x

₁

+x

₂

+x

₃

) x

₁か

x

₂ か

x

₃ の少なくとも

1

つが

1

すべて

0 =1

=0

(5)

5

x =1

f = (x

₁

+x

₂

) (x

₁

+x

₃

) (x +x ) (x

₁

+x

₃

)

だと

f =1

にできる。

（ ₁ ）

1 2

x

₂

=1 x

₃

=0

f = (x

₁

+x

₂

) (x

₁

+x

₂

) (x +x ) (x

₁

+x

₂

)

だと、どうやっても

f =1

にできない。

1 2

ＳＡＴの例

(6)

6

最小頂点被覆問題（判定問題版）

グラフ

G

と整数

K

が与えられて、

「

G

は頂点数

K

以下の頂点被覆を持つか？ＹＥＳ／ＮＯ？」

を問う。

K

＝４

YES

頂点の集合

C

で、どの枝も端点のどちらかが

C

に属する。

(7)

7

リダクションの概要

元の問題で

f =1

とできる

K

個以下の頂点で被覆できる

⇔

ＳＡＴＶＣ

f (G, K)

YES/NO YES/NO

高速（多項式時間）

？

？のところが高速ならば、全体としてＳＡＴに対する高速なアルゴリズムが作れたことになる。

YES NO

⇔ ⇔

つまり、

VC

に対する高速なアルゴリズムが存在すれば、

SAT

に対する高速なアルゴリズムも存在することになる。

逆に言えば、

SAT

を解く高速なアルゴリズムが存在しないならば、

VC

を解く高速なアルゴリズムも存在しない。

(8)

8

リダクションの概要

元の問題で

f =1

とできる

K

⇔

ＳＡＴＶＣ

f (G, K)

YES/NO YES/NO

高速（多項式時間）

？

ポイント：

f

を解いて、

YES

か

NO

か分かった後で

(G, K)

を作るのは簡単にできる。

しかし、

SAT

は難しい問題なので、

f

を解くだけで指数時間かかる。

f

を解かずに、答えが分からないまま「表面的な」変換だけで、

YES/NO

を保存させることが出来るのがミソ。

YES NO

⇔ ⇔

(9)

9

リダクションの方法

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

c

₁個

c

₂個

c

₃個

c

_m個

x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

…

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1)

(10)

10

元の問題で

f =1

とできる

K

…

⇔

どちらか1個選ばなければいけない。

全部で

n

個

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1) x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

c

₁個

c

₂個

c

₃個

c

_m個

(11)

11

…

c

₁

-1個選ばなければならない

c

₂

-1個選ばなければならない

c

_m

-1個選ばなければならない

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1) x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

c

₁個

c

₂個

c

₃個

c

_m個

元の問題で

f =1

とできる

K

⇔

(12)

12

…

この内部の枝はカバーできた。

2

つの間を繋ぐ枝をどうカバーするか

x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1)

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

(13)

13

このうち、

3

頂点は選べるので、間の枝のうち、

3

本は自動的にカバーできる

x

₂

…

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

これだけが残るので、

上でうまくカバーしてくれると嬉しい

(14)

14

…

内部の枝はカバーできた。

2

つの間を繋ぐ枝をどうカバーするか

x

₁

=1 x

₂

=1 x

₃

=0

1 1

x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1)

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

(15)

15

…

困るのは

x

₁

=0 x

₂

=1 x

₃

=0

0 0 0

x

₁

…

x

₁

x

₂

x

₂

x

₃

x

₃

x

₄

x

₄

x

₅

x

₅

x

_n

x

_n

K=n+(c

₁

-1)+(c

₂

-1)+…+(c

_m

-1)

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

) (x

₂

+x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

)

(16)

16

SAT

も

VC

も、「難しい問題」として知られている。

そういう問題が「

NP

完全問題」。

多項式時間アルゴリズムが存在しないだろうと思われている（が、まだ証明はされていない）。

グラフに関する

NP

完全問題は、

VC

以外にも数限りなくある。

・

k-

クリーク問題

・

k-

独立頂点集合問題

・

3

彩色問題

・ハミルトン閉路問題

(17)

17

P

と

NP

・

SAT

（入力：論理式

f

）

f

の全部の項を

1

にする変数割り当てがある？

YES? NO?

・最小頂点被覆問題（入力：グラフ

G

と整数

k

）

k

個の頂点を選んで、

G

のすべての枝をカバーできる？

YES? NO?

・最短経路問題（入力：重み付グラフ

G

、

2

頂点

s

と

t

、整数

k

）

s

から

t

まで、長さ

k

以下のルートがある？

YES? NO?

・最小全域木問題（入力：重み付グラフ

G

、整数

k

）

G

から枝を選んで、重みの合計が

k

以下の木を作れる？

YES? NO?

ここでは、答えが

YES

か

NO

を判定する判定問題だけを考える。

(18)

つまり、これら

4

つの問題は、全て

NP

に入る。 18

NP: Yes

の入力に「答が

Yes

である証拠」が与えられたら、

確かに

Yes

であることを多項式時間で検証できる。

また、

No

の入力に「答が

Yes

である証拠」が与えられても、

騙されない。

・

SAT

変数への

0/1

割り当てが与えられたら、それが全ての項を充足するか否かを、多項式時間で検証できる。

・最小頂点被覆問題

頂点集合が与えられたら、それが

k

個以下で、かつ、

正しい被覆になっているか否かを、多項式時間で検証できる。

・最短経路問題

s

から

t

へのルートが与えられたら、その長さが

k

以下であるか否かを、多項式時間で検証できる。

・最小全域木問題

木が与えられたら、それが全域木で、その重みが

k

以下であるか否かを、

多項式時間で検証できる。

(19)

19

P:

「答が

Yes

である証拠」が与えられなくとも、

Yes

であることを

（自力で）多項式時間で検証できる。

ダイクストラのアルゴリズムで最適解を求めて、それを

k

と比較すれば、

多項式時間で

YES

か

NO

か分かる。

・最小全域木問題

クラスカルのアルゴリズムで最適解を求めて、それを

k

と比較すれば、

多項式時間で

YES

か

NO

か分かる。

つまり、これら

2

つの問題は、

P

に入る。

SAT

や

VC

が

P

に入るかどうかは不明

(20)

20

P

は

NP

の部分集合

NP

P

多項式時間アルゴリズムを持つ問題の集合（易しい問題の集合）

・最小全域木問題など

答を多項式時間で検証できる問題の集合

・

SAT

・最小頂点被覆問題など

P=NP

か

P≠NP

かはまだ分かっていない。

（多くの人が

P≠NP

だろうと思っている。）

(21)

21

有名な未解決問題

（

21

世紀の

7

大未解決問題の

1

つ）

NP P

P≠NP

予想

・「

NP

と

P

は異なる、つまり、

NP

に入るが

P

に入らない問題が存在する」という予想。

・「与えられた答が正しい答であるかどうかの検証は簡単だが、

自分で答を見つけるのは難しい問題は存在する。」という意味も持つ。

(22)

22

…

(23)

23

ＳＡＴＶＣ

f (G, K)

YES/NO YES/NO

多項式時間

？

NP

完全性は、

P vs NP

問題を解く有力な手掛かり

SAT

から

VC

へのリダクション（前出）

これは、

VC

を解くアルゴリズムをサブルーチン（部品）として使って、

SAT

を解くアルゴリズムを構築していると解釈できる。

「？」の部分が多項式時間⇒全体が多項式時間

VC

が

P

に入る⇒

SAT

が

P

に入る

(24)

24

問題

A

が

NP

完全であるとは、

(1) A

自身が

NP

に入る。

(2) NP

のどの問題からも

A

にリダクション出来る。

※

世の中のたくさんの（何千、何万という）実用的な問題が、

NP

完全問題であるということが知られている。

A

定義の意味は、次のスライドで。

(25)

25

好きな

NP

完全問題

A

を選ぶ。

・

A

が

P

に入ることを示せば、

P=NP

を示したことになる。

リダクションの性質から、

NP

問題全てが

P

に入る。

A

なぜ

NP

完全性が、

P vs NP

問題に関係している？

・

A

が

P

に入らないことを示せば、

P≠NP

を示せたことになる。

A

は

NP

に入るのに

P

に入らないから。

つまり、

NP

は無数の問題を含んでいるが、

P vs NP

問題を考える上では、何でも良いからある

1

つの

NP

完全問題が多項式時間で

解けるか否かに集中すれば良い。

(26)

26

A B C

A

に対する入力

I

から

B

に対する入力

I’

を作る

R

₁

R

₂

R

₁ ：

B

に対する入力

I’

から

C

に対する入力

I’’

を作る

R

₂ ：

R

：

R

と

R

を使って、

A

に対する入力

I

から

C

に対する入力

I’’

を作る。¹ ²

問題

A

が

NP

完全であるのを示すとき、

(1)

を示すのは難しくないが、

(2)

は難しそうに思える。（

NP

の問題は無限にあるから。）

しかし、リダクションは推移的である。すなわち、

A

から

B

にリダクション出来て、

B

から

C

にリダクション出来れば、

A

から

C

にリダクション出来たことになる。

(27)

27

ある問題

X

が

NP

完全だということを示せたとしよう。

X

すると、問題

A

に対して

(2)

を示すには、

X

から

A

へのリダクションを見つけさえすれば良い。

なぜなら、前ページの議論より、全ての問題から（

X

を経由して）

A

にリダクションできることになるから。

A

最初に

NP

完全だということが示されたのが

SAT

。

それ以降は、

SAT

から芋づる式にリダクションして得られた。

(28)

28

3

彩色問題の

NP

完全性の証明

(1) NP

に入ることは明らか。与えられた

3

彩色に対して、

どの枝を見ても、その両端の色が異なっていることをチェックするのは、多項式時間で出来る。

(2)

任意の

NP

問題からリダクション出来ることについて。

既に

NP

完全であることが分かっている

3SAT

からリダクションする。

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

+ x

₂

) (x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

) SAT

の特殊なもの。各項に現れるリテラルの数がちょうど

3

のもの。

3

個

3

個

3

個

3

個

(29)

29

x

1

x

2

x

ⁿ

x

n

x

2

x

1

f= (x

₁

+x

₂

+ x

₃

) (x

₁

+ x

₅

+ x

₂

) (x

₃

+ x

₄

+x

₆

) … (x

₈

+ x

₉

+x

₁₂

) x

3へ

全ての項に対して同じように作る

v

₀

v

₁

(30)

30

x

1

x

2

x

ⁿ

x

n

x

2

x

1

2 0 1 1

1

0 0 0

1 1

x

i や

x

_i は

0

か

1

でしか塗れない

x

i を

0

、

x

_i を

1

か、またはその逆しかない。

前者を

x

_i

=0

、後者を

x

_i

=1

と解釈する。

v

₁

v

₀

(31)

31

項に対応する部分

0 0 0

0

変数部分が全部

0

ならば

ここには

0

を使わざるを得ない

0 1 0

0

変数部分に

1

つでも

1

があれば

ここを

1

で塗れる

（他の

6

つの場合も

正しいことを確かめよ）

1 1

2

0

(32)

32

3SAT

の入力

f

が

YES

。

→

全部の項を

1

とする変数割り当てに従って、変数頂点を

0

と

1

で塗る。

→

それぞれの項に対応する部分グラフを

0, 1, 2

で塗る。

（どの項も、

1

となる変数が少なくとも

1

つあるので、

正しく塗れる。）

→ 3

彩色問題の入力

G

が

YES

。

3

彩色問題の入力

G

が

YES

。

→

全ての頂点を

0, 1, 2

で正しく塗れる。

→ v

が

0

、

v

が

1

になるように、色を入れ替える。

→

各項に対応する部分グラフの一番左にある

3

頂点のうち、

少なくとも

1

つは色

1

で塗られている。

→

変数頂点の色（

0

または

1

）に従って、

f

の変数の

0/1

割り当てを決めると、各項少なくとも

1

つは

1

となる変数を含む。

→ 3SAT

の入力

f

が

YES

。

0 1

(33)

33