狠狠撸

P, NP, NP困難, NP完全
～前編～
2020/07/20
1

本題の前に???
家にある本のうち、P, NPについ
て記述されている本が右のものし
かありませんでした。しかし、こ
の本の中にはチューリング機械の
（ある程度厳密な）定義の話から
始まる難解な話しかなかったため、
今日はネットを参考にしたゆるふ
わな切り口で話します。厳密性は
無いものとしてお聞きください。
（厳密な定義が気になる方は、右
の本を読んでみてください。）
2

そもそも、どんな分野の話か
主に組合せ最適化に関する話。
組合せ最適化とは、（ざっくり説
明すると）与えられた任意の有限
集合の中から、ある条件を満たす
部分集合を見つける手法やその行
為自体のことを指す。
組合せ最適化では計算量が重要に
なってくる。P, NP等の用語は、こ
の計算量に関するものである。
3
計算量の違いによる実行時間
の増え方の例

P, NPとは？
決定問題（=答えがYESまたはNOのいずれかであるような問題、
判定問題とも言う）に関して、以下のように定義されている。
üクラスP：
多項式時間(POLYNOMIAL TIME)で解ける決定問題の集合
üクラスNP：
YESとなる証拠が与えられた時、その証拠が本当に正しいかど
うかを多項式時間で判定でき、また、非決定性多項式時間
(NON-DETERMINISTIC POLYNOMIAL TIME)で解ける決定
問題の集合
→ NPはNOT-Pではない！！！
4

P, NPとは？
クラスPとクラスNPの関係を図解すると以下のようになる。
5
P
NP
NPはPを包含している！

非決定性多項式時間???？
非決定性チューリングマシンによって多項式時間で解ける、と
いう意味。
非決定性チューリングマシン（対義語は決定性チューリングマシ
ンで、これは雑に言うと現実のコンピュータのこと）とは、次の
遷移状態が非決定的な計算機のことを指す。
余談：
量子コンピュータが「すげーすげー」ともてはやされる理由は、この非
決定性チューリングマシンの特性があるからである。量子コンピュータ
を使うと、今まで指数時間でしか解けなかった問題が多項式時間で解け
るようになる、と言われている。
6

力尽きました。
続きはまた次回???
7

狠狠撸

P, NP, NP困難, NP完全 ?前編?

More Related Content

P, NP, NP困難, NP完全 ?前編?