P 対 NP 問題（解決したら 100 万ドル）
奈良女子大学理学部情報科学科 鴨浩靖

2013 年 8 月 2 日

1

P 対 NP 問題とは？
強引な要約：
一般に、解が与えられたときにそれを十分に速く検算できる問題は、解が与えられなくても十分に速く解の有無を判定できるか？

未解決。答えが「はい」か「いいえ」か、わかっていない。
多くの研究者は、答えは「いいえ」だと思っている。
→ P 6= NP 予想とも呼ばれる。

2

余談：P 対 NP 問題が出てくる作品• 米国の TV ドラマ『NUMB3RS』（邦題：『NUMBERS
天才数学者の事件ファイル』）で、主人公の数学者が P対 NP 問題に挑戦するシーンがある。
• 日本の推理小説『容疑者 X の献身』（東野圭吾）にも、登場人物が P 対 NP 問題について語るシーンがある。

3

ミレニアム懸賞問題
クレイ数学研究所が 2000 年に懸賞をかけた。
賞金は各 100 万ドル。

◦ P 対 NP 問題◦ ホッジ予想◦ リーマン予想◦ バーチ・スウィナートン-ダイナー予想
F ポアンカレ予想（解決済み。賞金を辞退）◦ ヤン・ミルズ理論と質量ギャップ◦ ナビエ・ストークス方程式
4

余談：100 万ドルが受賞者に渡るまで(1) 解決した人の論文が、世界的に評価された査読付き数学専門雑誌に掲載される。
(2) 2 年待つ。
(3) 2 年経って、解決が数学界に受け入れられたとみなされるな
らば、クレイ数学研究所科学諮問会議が、その問題についての特別諮問委員会を設置する。
(4) 特別諮問委員会の報告をもとに科学諮問会議がさらに検討を加え、研究所の理事会に勧告を出す。
(5) 科学諮問委員会の勧告に基づき、理事会が授賞の決定をする。
(6) 受賞者が賞金を受け取る。
5例：オイラー路（一筆書き）の有無を判定する
すべての辺をちょうど一度ずつ通る路は存在するか？

1.

2.

3.

6

4.

Leonhard Euler (1707–1783)

7

しらみつぶしでオイラー路の有無を判定する方法
辺の順列をすべて生成して、ひとつひとつ判定する。

1432

1-2-3-4 ×

1-2-4-3 ×

1-3-2-4 ○1-3-4-2 ×

1-4-2-3 ○1-4-3-2 ×

2-1-3-4 ×

2-1-4-3 ×

2-3-1-4 ○2-3-4-1 ×

2-4-1-3 ○2-4-3-1 ×

3-1-2-4 ×

3-1-4-2 ○3-2-1-4 ×

3-2-4-1 ○3-4-1-2 ×

3-4-2-1 ×

4-1-2-3 ×

4-1-3-2 ○4-2-1-3 ×

4-2-3-1 ○4-3-1-2 ×

4-3-2-1 ×

8

判定してみる
S3S4S5S6S7S8...
これらを対象に実験する。
9オイラー路の有無のしらみつぶし法での計算時間

グラフ

辺の数

計算時間

S3

30.01 秒未満 (実測)S440.01 秒未満 (実測)S550.01 秒未満 (実測)S660.01 秒未満 (実測)S770.01 秒未満 (実測)S880.01 秒未満 (実測)S990.01 秒(実測)

S10

100.12 秒

(実測)

10

グラフ

辺の数

計算時間

S11

111.37秒(実測)

S121216.57秒

(実測)

S13

133 分 32.98秒

(実測)

S14

1449 分 39.97秒(実測)

S1515 12 時間 29 分 26.99秒

(実測)

S16

168.3日(推計)

S171720週

(推計)

S18

187.0年

(推計)

11

グラフ

辺の数

計算時間

S19

19130年(推計)

S20202700年

(推計)

S21

21

5 6000年

(推計)

S22

22

120 0000年

(推計)

S23

23

2800 0000年

(推計)

S24

24

6 8000 0000年(推計)（宇宙の年齢137 0000 0000年）

S25

170 0000 0000年

(推計)

25

12

グラフ

辺の数

計算時間

S26

26

四千億年

(推計)

S27

27

十兆年

(推計)

S28

28

三百兆年

(推計)

S29

29

一京年

(推計)

S30

30

三十京年

(推計)

S31

31

九百京年

(推計)

S32

32

三垓年..
.

(推計)

S62

62

三百無量大数年

(推計)

S63

63

（ここから先、日本語がない）

..
.

13

辺の数 15（約半日）が実用上の限界。

14

辺の数 30（約三十京年）が実用的になるように高速化するには、計算機の性能を約一垓倍にしなくてはならない。

しらみつぶし法では無理！

15オイラー路の有無を判定する効率の良い方法
グラフがオイラー路を持つ必要十分条件は、以下の二つとも成り立つこと。

• 奇数本の辺が集まる頂点が 0 個か 2 個である。
• 全体が連結である。すなわち、どの二つの頂点も辺をたどって行き来できる。
この定理を利用すれば、効率の良い判定プログラムを書くことができる。

16

1.

2.

3.

4.

奇点

2個4個0個2個

連結性

連結

連結

連結

不連結

オイラー路あり

なし

あり

なし

17

オイラー路の有無を判定する効率の良い方法の計算時間

グラフ

辺の数計算時間S3

30.01秒未満

(実測)

S30

300.01秒未満

(実測)

S300

3000.01秒未満

(実測)

S3000

30000.01秒未満(実測)

S300003 00000.04秒(実測)

S300000

30 00000.55秒(実測)

S3000000

300 0000

6.20秒(実測)S30000000

3000 0000

70.01秒

(実測)

18

疑い
早く計算が終わるデータを選んでいるのではないの？

19釈明
以下のことが数学的に証明できる。
計算機の性能によって決まる定数 a があって、辺の本数が n であるグラフが入力されると「効率の良いオイラー路判定プログラム」は計算時間 an [秒] 以下でオイラー路の有無を判定できる

20

例：ハミルトン路（別種の一筆書き）の有無を判定する
すべての頂点をちょうど一度ずつ通る路は存在するか？

1.

2.

3.

21

4.

William Rowan Hamilton (1805–1865)22

ハミルトン路の有無をしらみつぶしで判定する方法

頂点の順列をすべて生成し、ひとつひとつ判定する。

42

13

1-2-3-4 ×

1-2-4-3 ×

1-3-2-4 ○1-3-4-2 ×

1-4-2-3 ○1-4-3-2 ×

2-1-3-4 ×

2-1-4-3 ×

2-3-1-4 ○2-3-4-1 ×

2-4-1-3 ○2-4-3-1 ×

3-1-2-4 ×

3-1-4-2 ○3-2-1-4 ×

3-2-4-1 ○3-4-1-2 ×

3-4-2-1 ×

4-1-2-3 ×

4-1-3-2 ○4-2-1-3 ×

4-2-3-1 ○4-3-1-2 ×

4-3-2-1 ×23

ハミルトン路の有無のしらみつぶし法での計算時間

グラフ

頂点の数

計算時間

S3

40.01 秒未満

(実測)

S4

50.01 秒未満

(実測)

S5

70.01 秒未満

(実測)

S6

70.01 秒未満

(実測)

S7

80.01 秒未満

(実測)

S8

90.01 秒

(実測)

S9100.10 秒(実測)

S10111.16 秒(実測)

24グラフ

頂点の数

計算時間

S111213.80秒(実測)

S12132 分 52.30秒(実測)

S131440 分 8.24秒(実測)

S1415 9 時間 43 分 1.21秒(実測)

S15166.4日(推計)S161716週(推計)

S17185.3年

(推計)

S18

199.9年(推計)

S19

20200年(推計)

25

ハミルトン路の有無を判定する効率の良い方法未発見。
しらみつぶしよりも多少はましな方法はみつかっている。
改良の研究は続行中

26

P 問題
計算機の性能に よって 決まる定数 a と計算機の性能に よらずに 決まる定数 k があって、大きさが n のデータが入力されると計算時間 ank [秒] 以下で解の有無を判定できるプログラムを書くことができる問題を P 問題という。

• オイラー路問題は P 問題。

27

EXP 問題
計算機の性能に よって 決まる定数 a と計算機の性能に よらずに 決まる定数 c と定数 k があって、大きさが n のデータが入力されるとnk
計算時間 ac [秒] 以下の解の有無を判定できるプログラムを書くことができる問題を EXP 問題という。

• ハミルトン路問題は EXP 問題。

28

P 問題と EXP 問題の関係• P 問題は EXP 問題でもある。
• EXP 問題であるが P 問題でない問題が存在することは証明済み。
• 計算可能であるが EXP 問題ですらない問題が存在することは証明済み。
EXP
P

29

NP 問題
計算機の性能に よって 決まる定数 a と計算機の性能に よらずに 決まる定数 k があって、大きさが n のデータが入力され、入力に加えて解も与えられると、計算時間 ank [秒] 以下で本当に解であると確認できるプロ
グラムを書くことができる問題を NP 問題という。

• ハミルトン路問題は NP 問題。

30

P 問題と NP 問題と EXP 問題の関係• P 問題は NP 問題でもある。
• NP 問題は EXP 問題でもある。
• EXP 問題であるが P 問題でない問題が存在することは、わかっている。（前述）• EXP 問題であるが NP 問題でない問題が存在するかどうかは不明。
• NP 問題であるが P 問題でない問題が存在するかどうかは不明。← P 対 NP 問題

31

NP=EXPEXPP

P=NPどれが正しい？

32

EXP
NP
P

ちょっと一般的でない言葉の使い方に注意
難しい 計算に時間がかかる
易しい 計算に時間がかからない
手順が複雑／単純理解が困難／容易などの意味は含まない。

33

厳密な言葉の使い方に注意（問題が）解ける うまくプログラムを書けば、どんな入力データに対しても、かならず計算結果が出力されるようにできる。
「一部の例外的な入力データについては計算できません」
はダメ！

34

難しい問題を比較したい
難しい問題は、一様に難しいか？
たぶん、そんなことはない。

• 普通に難しい問題• とても難しい問題• 極めて難しい問題• 著しく難しい問題などなどがあると思う。
難しい問題の難しさの程度を比較したい！
35

難しい問題を比較する
問題 α も問題 β も難しい問題とする。
問題 β を一瞬で解くことのできる計算機 M が存在すると、現実に反して仮定する。この仮定の下で、架空の計算機 Mをうまく使ってやると、問題 α があたかも P 問題であるかのように解けるとする。

36

α を多項式時間で解く
β を一瞬で解く

M利用者

このような架空の計算機複合体を考えることができるとき、
問題 α の難しさは問題 β の難しさ以下である（問題 β の難しさは問題 α の難しさ以上である）と定義する。
37

問題 α の難しさが問題 β の難しさ以下であり、同時に、問題 α の難しさが問題 β の難しさ以上であるとき、
問題 α は問題 β と同程度に難しいと定義する。
問題 α の難しさが問題 β の難しさ以上であり、問題 α は問題 β と同程度に難しくはないとき、
問題 α は問題 β より真に難しいと定義する。

注意：難しさが比較不能な場合もある。

38

NP 困難問題 ϕ の難しさが、どんな NP 問題 α についてもその難しさ以上であるとき、問題 ϕ を NP 困難な問題と呼ぶ。

39

NP 完全問題
NP 困難な NP 問題を、NP 完全問題と呼ぶ。

40

NP 完全問題
NP 完全問題は、いわば、NP 問題の頂点に君臨する難しさの問題。
1971 年に充足可能性問題（略称：SAT）が NP 完全であることが証明されて以来、NP 完全問題が続々と発見され続けている。

41

NP 完全な問題の例—SAT
変数 x1 , . . . , xk から ¬ と∧ と ∨ を使って作られた式が与えられたとき、x1 ,. . . , xk のそれぞれに 0 か1 をうまく割り当てて、式の値を 1 にできるか？

x ¬xx yx∧y x∨y010 000100 1011 0011 111

例 x1 ∧ ¬(¬x1 ∨ x2 ) ∧ (¬x1 ∨ x3 ) には、x1 = 1,x3 = 1 と割り当てればよい。

42x2 = 0,NP 完全な問題の例—ハミルトン路与えられたグラフに、すべての頂点をちょうど一度ずつ通る路は存在するか？

43

NP 完全な問題の例—k クリーク
与えられたグラフから k 個の頂点を選び、その k 個のうちのどの 2 個も結ばれているようにすることができるか？

3 クリークはあるが、4 クリークはない。

44

NP 完全な問題の例—三色塗り分け与えられたグラフのそれぞれの頂点を赤、緑、青のどれかの色に塗り、結ばれている頂点は必ず異なる色にすることができるか？

45

NP 完全な問題の例—
二次ディオファントス方程式
与えられた正整数 a, b, c について、未知数 x, y の方程式
ax2 + by = c は正整数解をもつか？

46

NP 完全な問題の例—その他応用上、重要そうな問題も多い。

• 巡回セールスマン問題• 各種の詰め込み問題• 各種のスケジューリング問題
..
.

47

P 対 NP 問題の解決への見通し（否定的解決への道）［証明済み］NP 完全問題の どれか一つ について、実は P問題であることを、実際にプログラムを書く方法で証明できれば、P = NP と結論づけられる。

→ でも、たぶん、P 6= NP だろうから、この方向は無理筋だろうなあ。

48

P 対 NP 問題の解決への見通し（初期の願望と挫折）（既知の事実） P 6= EXP は対角線論法を使って証明できる（願望） P 6= NP も対角線論法を使って証明したい（挫折） 「P 6= NP も P = NP も対角線論法を使う方法では証明できない」が証明された（大団円ではない） 他の手法を模索中

49

P 対 NP 問題の解決への見通し（有力な候補）• 代数幾何が役に立つのではないか？
• 論理体系に帰着させることはできないか？

50

P 対 NP 問題の解決への見通し（現状）「○○の方法では証明できない」を着々と発見中。

51

おおざっぱな歴史 (1)1936 年 「計算」の定義が確立される（チャーチ、チューリング、他多数）

1971 年 P 対 NP 問題が定式化される（クックとレビンが独立に発見）
2000 年 P 対 NP 問題がミレニアム懸賞問題に選ばれる
2013 年 P 対 NP 問題は未解決
52

おおざっぱな歴史 (2)40000 年前? ヒトが何かを数えた痕跡が遺される。
5000 年前? 最古の数字？（メソポタミア文明）
1500 年前? インドで 0 が発見され、位取り記数法による計算が可能になる。
77 年前 「計算」の定義が確立する。
現在53

「計算」の定義が確立して、すぐにできたこと
関数の分類関数計算可能な関数






計算不可能な関数





54

次にしたくなること
細かい分類関数

計算可能な関数










計算不可能な関数








55




ここを細かく分類するのが








計算可能な関数
計算量理論







計算複雑性理論ともいう
関数

ここを細かく分類するのが







計算不可能な関数
帰納的関数論







再帰関数論ともいう

56

計算量クラス
P、NP、EXP の他にも、問題の難しさの分類はたくさんある。これらを計算量クラスという。
Complexity Zoo
https://complexityzoo.uwaterloo.ca/Complexity Zooには 495 個掲載されている。

計算量クラスの包含関係については、未解決の問題が多数ある。P 対 NP 問題もそのひとつ。

57

まとめ
• P 対 NP 問題とは、一般に、解が与えられたときにそれを十分に速く検算できる問題は、解が与えられなくても十分に速く解の有無を判定できるか？

• P 対 NP 問題は未解決。
• P 対 NP 問題は、壮大な問題
計算量クラスの階層構造を確定せよの一部。

58