旅好きおやじの日記 TOP  >  自然科学・工学  >  数学 >  「P≠NP」問題

「P≠NP」問題

数学上の未解決問題のうち、解いたら100万ドルの懸賞金が与えられると
いうミレニアム懸賞問題といものがあり、有名なリーマン予想と共に、難問
に挙げられるP≠NP予想というものがある。

P≠NPが何なのかを知るためには、グラフというものを知る必要がある。

グラフとは点と辺でつないだものをいい、以下の様なものである。
graph_201605.jpg

グラフの中で、すべての辺を1回だけ通る道をオイラー路という。
いわゆる一筆書きできるかというものである。
上に挙げたグラフでは一筆書きできないのでオイラー路はない。

次に全ての節点(赤い点)を1回通る道をハミルトン路という。
上のグラフでは赤い点を1回だけ通る道は簡単に見つかるだろう。

どちらもアルゴリズムなど駆使しなくても解けるか解けないかが簡単にわかる
問題である。

これが次のようなグラフになってくるとどうだろうか?
O_44.gif

これはそう簡単にはわからないだろう。

アルゴリズムには、計算量という概念がある。

計算をする対象の数、ここでいう辺とか節点の数をnとした場合、その
計算量がn2とか、n3で解けるものを多項式時間といい、
計算量が2nとか、3nで解けるものを指数関数時間という。

この2とか3とかいう数が10とか20とかになってくると、指数関数時間の
アルゴリズムは爆発的な計算量が必要になる。

一筆書きのオイラー路の計算のような計算は多項式時間の計算量なので、
P問題のひとつである。
ハミルトン路の方は、多項式時間の計算量かどうかは不明だが、
答えが与えられていたら簡単だという問題に分類され、NP問題のひとつ
である。

解がある問題(NP問題)ではあるが、それが全て多項式時間で求められる
問題(P問題)なのかどうか?恐らく、P≠NPのものもあるだろうという予想が
立てられているが、それが正しいかどうか証明されていない。

これが、もし、証明されていたら、素因数分解の複雑さを利用したような
暗号化のアルゴリズムも何らかの工夫をすれば見つかるということを意味し、
それが見つかっていないのだからP≠NPだと考えられている。


以下の本を読んだが、この本は冗長な解説である最初の100ページを
読み飛ばして読むと何となく、雰囲気をつかむことができた。




関連記事
組合せ爆発とおねえさん(2015/8/11)
http://yama2190.blog.fc2.com/blog-entry-1707.html

スポンサーサイト


最後まで読んで頂きありがとうございます。こちらを押していただけると嬉しいです!!
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
にほんブログ村 オヤジ日記ブログへ
コメントの投稿












管理者にだけ表示を許可する
カテゴリ

openclose

プロフィール

旅好きおやじの日記

Author:旅好きおやじの日記
職業はIT関係です。
趣味は海外旅行(22カ国制覇)、読書、資格取得です。
取得した資格は以下のとおりで、半分趣味のようになってます。

・情報処理
 ・ITストラテジスト
 ・システム監査
 ・プロジェクトマネージャ
 ・アプリケーションエンジニア
 ・テクニカルエンジニア(システム管理)
 ・テクニカルエンジニア(データベース)
 ・ネットワークスペシャリスト
 ・エンベデッドシステムスペシャリスト
 ・情報セキュリティアドミニストレータ
 ・情報処理一種
 ・情報処理2種
 ・情報セキュリティマネジメント
 ・ITパスポート
・元PMP
・ITIL V3 Foundation
・Oracle Master Gold
・日商簿記1級
・建設業経理士1級
・英検2級

最新記事
カレンダー
プルダウン 降順 昇順 年別

08月 | 2017年09月 | 10月
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30



ブクログ
楽天
アクセスランキング
[ジャンルランキング]
日記
739位
アクセスランキングを見る>>

[サブジャンルランキング]
会社員・OL
159位
アクセスランキングを見る>>
検索フォーム
人気ブログランキング
ブロとも申請フォーム