第12幕・NP完全問題
文字数 1,246文字
「NP完全問題とは,NP問題の一部を構成する問題の事です。
世の中には,NP完全問題が溢れている事が知られています。
例えば,テトリスやぷよぷよなどのテレビゲーム,ジグソーパズルや数独などのパズル,ビジネス分野では宅配便の最適経路問題,正確にはハミルトンパス問題などです。
もしかしたら,世界は様々なNP完全問題が複雑に絡み合って出来ているかも知れませんね?
また,NP完全問題は,P≠NP問題の解決の糸口になるのではないかと専門家の間では以前から注目されているのです。すなわち,無数にあるNP完全問題の内,どれか一つでも,クラスPに属することが示されれば,P=NPが証明されたことになるからです。
でも,これ以上詳しく解説すると,と~ても,長くなるので,ここではNP問題の特別なバージョンの一つと思ってくださいね。
どうしても詳しく知りたい人は,私,高坂杏が推薦する専門書を読んでくださいね。
きっと,貴方を未知のアドベンチャーワールドに誘う一冊になりますよ。」
杏は人差し指を立てながら,杏のベッドの上にいるオイラーに話しかけた。しかもウィンク付きで。
そう,ここは杏の部屋である。
杏は,バラエティ番組のレポーター&解説者の気分だった。しかし,唯一の視聴者たるオイラーは,それがどうした?と言わんばかりに,大きなあくびをしてから,目を閉じてまどろみはじめた。
そんなオイラーのリアクションを見た杏は,立てた人差し指を所在なげに回しはじめた。
「オイラー,君も数学者の端くれなら,もう少しこの遊びにノッてくれてもいいんじゃない?」などと杏はオイラーに悪態をついたが,当のオイラーは既に夢の中の住民と化していた。
杏は,そんなオイラーを,頬を膨らましながら睨んでから,自分の部屋の床に厚く堆積した紙をあさりだした。
確かこの辺に,アイディアを考えていた時のメモ,数独を例題に定式化を検証していた時のメモがあったはずなんだけど。どれかなぁ~。
宝物探しタイムに,心弾む杏。
しかし,結菜に言わせれば,ちゃんと分類整理してバインダーに綴じて,背表紙をつけていれば,一瞬で見つかるはずの宝物探しなのだが。。。
あっ,これは回路計算量で数独を検討していた時のメモだ!これも使えるわねぇ。
おっ,これは代数化で定式化したときのメモを発見!!
我ながら,頑張ったわよね~ぇ。
で,本命くんはどこかなぁ~。
あったー!!
我,宝物庫の鍵を開けたり!!
さぁ~て,一丁,論文を書きましょうかぁ。
幸いなるかな,明日からは冬休み!幾らでも時間があるんじゃないかぁ!
でも,年賀状書きが残っていたから,27日までにアップロードしよう!
杏は勉強机のパソコンに向かって
「では,我が華麗なるキータイプを受けるが良い。」と掛け声を掛けてから,おもむろに論文を書きはじめた。
杏は,ハミングとひとり言を奏でながら書いている論文が,セルゲイに更なる苦悩とともに変革を迫ることになろうとは,露ほども考えていなかったのだ。
世の中には,NP完全問題が溢れている事が知られています。
例えば,テトリスやぷよぷよなどのテレビゲーム,ジグソーパズルや数独などのパズル,ビジネス分野では宅配便の最適経路問題,正確にはハミルトンパス問題などです。
もしかしたら,世界は様々なNP完全問題が複雑に絡み合って出来ているかも知れませんね?
また,NP完全問題は,P≠NP問題の解決の糸口になるのではないかと専門家の間では以前から注目されているのです。すなわち,無数にあるNP完全問題の内,どれか一つでも,クラスPに属することが示されれば,P=NPが証明されたことになるからです。
でも,これ以上詳しく解説すると,と~ても,長くなるので,ここではNP問題の特別なバージョンの一つと思ってくださいね。
どうしても詳しく知りたい人は,私,高坂杏が推薦する専門書を読んでくださいね。
きっと,貴方を未知のアドベンチャーワールドに誘う一冊になりますよ。」
杏は人差し指を立てながら,杏のベッドの上にいるオイラーに話しかけた。しかもウィンク付きで。
そう,ここは杏の部屋である。
杏は,バラエティ番組のレポーター&解説者の気分だった。しかし,唯一の視聴者たるオイラーは,それがどうした?と言わんばかりに,大きなあくびをしてから,目を閉じてまどろみはじめた。
そんなオイラーのリアクションを見た杏は,立てた人差し指を所在なげに回しはじめた。
「オイラー,君も数学者の端くれなら,もう少しこの遊びにノッてくれてもいいんじゃない?」などと杏はオイラーに悪態をついたが,当のオイラーは既に夢の中の住民と化していた。
杏は,そんなオイラーを,頬を膨らましながら睨んでから,自分の部屋の床に厚く堆積した紙をあさりだした。
確かこの辺に,アイディアを考えていた時のメモ,数独を例題に定式化を検証していた時のメモがあったはずなんだけど。どれかなぁ~。
宝物探しタイムに,心弾む杏。
しかし,結菜に言わせれば,ちゃんと分類整理してバインダーに綴じて,背表紙をつけていれば,一瞬で見つかるはずの宝物探しなのだが。。。
あっ,これは回路計算量で数独を検討していた時のメモだ!これも使えるわねぇ。
おっ,これは代数化で定式化したときのメモを発見!!
我ながら,頑張ったわよね~ぇ。
で,本命くんはどこかなぁ~。
あったー!!
我,宝物庫の鍵を開けたり!!
さぁ~て,一丁,論文を書きましょうかぁ。
幸いなるかな,明日からは冬休み!幾らでも時間があるんじゃないかぁ!
でも,年賀状書きが残っていたから,27日までにアップロードしよう!
杏は勉強机のパソコンに向かって
「では,我が華麗なるキータイプを受けるが良い。」と掛け声を掛けてから,おもむろに論文を書きはじめた。
杏は,ハミングとひとり言を奏でながら書いている論文が,セルゲイに更なる苦悩とともに変革を迫ることになろうとは,露ほども考えていなかったのだ。