なぜ P ? なぜ NP ?
ある問題が易しいか難しいか．
⇐ ⇒
その問題を解くための「良い」アルゴリズムがあるのか無いのか．
1.
もしその問題の解を求めるための多項式時間アルゴリズムが見つかれば，そ の問題を解くことは容易(
つまりその問題はP
に属する)
2.
もしその問題の解を求めるための多項式時間アルゴリズムが見つからなけ れば …= ⇒
実は，こちらはちょっとややこしい∵
多項式時間アルゴリズムが見つからないからと言って，その問題が 容易でない
( P
に属さない)
とは言えない．
なぜ P ? なぜ NP ?
ある問題が易しいか難しいか．
⇐ ⇒
その問題を解くための「良い」アルゴリズムがあるのか無いのか．
1.
もしその問題の解を求めるための多項式時間アルゴリズムが見つかれば，そ の問題を解くことは容易(
つまりその問題はP
に属する)
2.
もしその問題の解を求めるための多項式時間アルゴリズムが見つからなけ れば …= ⇒
実は，こちらはちょっとややこしい∵
多項式時間アルゴリズムが見つからないからと言って，その問題が 容易でない
( P
に属さない)
とは言えない．
不可能性の証明は一般に難しい 努力が足りないだけかもしれない
なぜ P ? なぜ NP ?
ある問題が易しいか難しいか．
⇐ ⇒
その問題を解くための「良い」アルゴリズムがあるのか無いのか．
1.
もしその問題の解を求めるための多項式時間アルゴリズムが見つかれば，そ の問題を解くことは容易(
つまりその問題はP
に属する)
2.
もしその問題の解を求めるための多項式時間アルゴリズムが見つからなけ れば …= ⇒
実は，こちらはちょっとややこしい∵
多項式時間アルゴリズムが見つからないからと言って，その問題が 容易でない
( P
に属さない)
とは言えない．
不可能性の証明は一般に難しい 努力が足りないだけかもしれない
なぜ P ? なぜ NP ?
ある問題が易しいか難しいか．
⇐ ⇒
その問題を解くための「良い」アルゴリズムがあるのか無いのか．
1.
もしその問題の解を求めるための多項式時間アルゴリズムが見つかれば，そ の問題を解くことは容易(
つまりその問題はP
に属する)
2.
もしその問題の解を求めるための多項式時間アルゴリズムが見つからなけ れば …= ⇒
実は，こちらはちょっとややこしい∵
多項式時間アルゴリズムが見つからないからと言って，その問題が 容易でない
( P
に属さない)
とは言えない．
不可能性の証明 は一般に難しい 努力が足りないだけかもしれないなぜ P ? なぜ NP ?
ある問題が易しいか難しいか．
⇐ ⇒
その問題を解くための「良い」アルゴリズムがあるのか無いのか．
1.
もしその問題の解を求めるための多項式時間アルゴリズムが見つかれば，そ の問題を解くことは容易(
つまりその問題はP
に属する)
2.
もしその問題の解を求めるための多項式時間アルゴリズムが見つからなけ れば …= ⇒
実は，こちらはちょっとややこしい∵
多項式時間アルゴリズムが見つからないからと言って，その問題が 容易でない
( P
に属さない)
とは言えない．
不可能性の証明 は一般に難しいP = NP か P , NP か，それが問題だ
P = NP
かP , NP
かは未解決である．注
1 P ⊆ NP
ではある．
–
非決定性アルゴリズムに決定性アルゴリズムは含まれる．–
直感で解く方(
非決定性アルゴリズム)
が優れているはず．注
2
多分P , NP
と信じられている．
–
この世には，解くことが難しいと考えられる問題が沢山存在する．–
これらの問題に対して，P
のオーダのアルゴリズムが見つかっていない．☞
不可能性の証明は難しい．–
但し，信じられているだけで証明されていない．注
3
従って、解決すれば有名になれる( + 100
万ドル
)
．–
否定的，肯定的どちらでも良い．–
クレイ数学研究所(Clay Mathematics Institute)
ミレニアム懸賞問題
(Millennium Problems)
の一つP = NP か P , NP か，それが問題だ
P = NP
かP , NP
かは未解決である．注
1 P ⊆ NP
ではある．–
非決定性アルゴリズムに決定性アルゴリズムは含まれる．–
直感で解く方(
非決定性アルゴリズム)
が優れているはず．注
2
多分P , NP
と信じられている．
–
この世には，解くことが難しいと考えられる問題が沢山存在する．–
これらの問題に対して，P
のオーダのアルゴリズムが見つかっていない．☞
不可能性の証明は難しい．–
但し，信じられているだけで証明されていない．注
3
従って、解決すれば有名になれる( + 100
万ドル
)
．–
否定的，肯定的どちらでも良い．–
クレイ数学研究所(Clay Mathematics Institute)
ミレニアム懸賞問題 の一つ
P = NP か P , NP か，それが問題だ
P = NP
かP , NP
かは未解決である．注
1 P ⊆ NP
ではある．–
非決定性アルゴリズムに決定性アルゴリズムは含まれる．–
直感で解く方(
非決定性アルゴリズム)
が優れているはず．注
2
多分P , NP
と信じられている．–
この世には，解くことが難しいと考えられる問題が沢山存在する．–
これらの問題に対して，P
のオーダのアルゴリズムが見つかっていない．☞
不可能性の証明は難しい．–
但し，信じられているだけで証明されていない．注
3
従って、解決すれば有名になれる( + 100
万ドル
)
．–
否定的，肯定的どちらでも良い．–
クレイ数学研究所(Clay Mathematics Institute)
ミレニアム懸賞問題
(Millennium Problems)
の一つP = NP か P , NP か，それが問題だ
P = NP
かP , NP
かは未解決である．注
1 P ⊆ NP
ではある．–
非決定性アルゴリズムに決定性アルゴリズムは含まれる．–
直感で解く方(
非決定性アルゴリズム)
が優れているはず．注
2
多分P , NP
と信じられている．–
この世には，解くことが難しいと考えられる問題が沢山存在する．–
これらの問題に対して，P
のオーダのアルゴリズムが見つかっていない．☞
不可能性の証明は難しい．–
但し，信じられているだけで証明されていない．注
3
従って、解決すれば有名になれる( + 100
万 ドル)
．–
否定的，肯定的どちらでも良い．–
クレイ数学研究所(Clay Mathematics Institute)
ミレニアム懸賞問題 の一つ
ドキュメント内
pla85900.tsp.eps
(ページ 77-86)