P、NP問題に関するMichael Sipser MIT教授の講義

Beyond Computation: The P vs NP Problem – Michael Sipser

2006年10月3日、ハーバード大学にて　

18分～P,NP問題の説明
P　”Polynomial time”
Quickly solvable problems
NP “Nondeterministic Polynomial time”
Quickly checkable problems
Includes the search problems

クラスPとは、決定性チューリング機械において、多項式時間で判定可能な問題のクラス
クラスNPは、Yesとなる証拠が与えられたとき、多項式時間でWitnessの正当性の判定（検証）が可能な問題のクラス
(ウィキペディア）

21分～P,NP問題の歴史的経緯について
25分～ゲーデルがフォン・ノイマンに宛てた手紙について
30分～クレイミレニアム懸賞問題
34分～primality test