P、NP問題

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