月別アーカイブ: 2017年4月

NP困難とNP完全

最近,証明書が切れたみたいでこのページが危険だって表示されるらしい.そろそろ更新しなきゃと思いつつ,何もしてない(めんどくさい).

さて,今回はNP困難とNP完全の話.よく間違えるので書こうと思います(間違えるのはもしかして俺だけ?).

計算量を議論する際に,知ってる人も多いと思うけれどPとNPという問題のクラスが存在する.Pは多項式時間で解ける問題を表していて,NPは答えを知っているときに問題を多項式時間で検証できる問題を意味してる.多項式時間が英語でPolynomial Timeなので,頭文字を取ってきてPだと思うのはいいけれど,NPをNon Polynomial Timeと考えて,多項式時間じゃない問題だと考えるのは間違い.

NPはNon Polynomial Timeじゃなくて,Non-deterministic Polynomial Timeのこと.意味が違うから勘違いしてはいけない.ただこの紛らわしい命名規則がそもそもの混乱の元のような気がする.

さて,多項式時間で解けるとは一体何を指しているのだろうか.これは簡単に言えば,問題のサイズに対して多項式に比例する時間で解けるという意味.例えばソートの問題であれば,性能の悪いソートアルゴリズムは要素数\(n\)に対して,大体\(n^2\)に比例する時間でソートができる.多項式ってのが例えば\(x^3+2x^2+x+-1\)みたいな形をしてるものを指してることを考えれば,できるの悪いソートアルゴリズムの計算時間が多項式時間であることがわかる.対して,各家庭に宅配をする問題を考えてみる.宅配をしなくちゃいけない家のリストとそれぞれの家の間の距離が与えられたときに,最短で回れるルートを考える問題はめちゃくちゃ難しくて,愚直にやると家の数\(x\)に対して,\(x!\)の時間がかかる.これは多項式じゃないので多項式時間で解けるとは言わない.

基本的には,問題のサイズ(例えば要素数が\(n\)とか)に対して,\(n^a+n^b+…+n^z\)(ただしa,b,…,zは定数)で解ければ,多項式時間で解けるってことになる.多項式時間の場合は別に,このaとかbの値がどのくらいの大きさであってもかまわないので,これがめちゃくちゃ大きければ解くのが大変なわけだけど,それでも宅配の問題のような\(n!\)みたいなのが出てこない限り,ときやすいと考える(たぶん).

Pの問題は多項式時間で解けるものを指しているけれど,NPは答えを与えられたときに多項式時間で検証できるものを表している.多くの場合,答えが与えられたらそれがあってるかどうかを検証することは,答えを見つけることより簡単なことが多い.例えばソートの問題だったら,ソートするよりソートが終わってるかどうかを調べるほうが断然簡単なのは明らかだ.だから,ソートの問題はPにもNPにも属していることになる.

他の問題に部分和問題がある.これは,複数個の数が与えられたときに,そこから幾つか選んで足したものが,ある数\(N\)に等しくなるように選ぶことができるかっていう問題.簡単な例として,1,5,7が与えられてたとしよう.ここからいくつか選んで足し合わせたら6にできるかって聞かれたら,即座に1と5を選べばいいってわかると思う.似たように今度は9にできるかって聞かれたら,できないってこともわかる.ただし,これは個数が少ないからわかるのであって,これが膨大な数から選択する問題だったら,簡単じゃない.ただし,膨大な数が渡されていたとしても,答えがわかっていてそれがあってるか確認するのならきっと直ぐにできる.実際,この問題はNPに属していて,さらにNPの問題の中では特に難しい問題だとわかってる.こういうのをNP完全という.

問題が難しいか簡単かという話は,ある問題を多項式時間で別の問題に帰着できるかどうか判断できる.例えば,幾つかの要素の中から最小のものを探したいとしよう.これは要素すべてを調べればわかるから,要素数\(n\)に計算時間が比例する.だけど,要素全体をソートしてから,一番端にある要素を取ってきても同じことができる.ソートするには一番速くて\(n \log(n)\)の時間がかかることがわかってるので,ソートするほうが遠回りになる.でもソートすることでも解けるということで,最小値を求める問題は,ソート問題に帰着できると言える.この例の通り,帰着元の問題は,帰着先の問題より簡単なので,帰着関係で問題の難しさを言うことができる.似たように難しさがわからない問題があったら,計算量が分かってる問題に帰着させる方法を考えればいい.

NP困難の問題は,クラスNPの中で特に難しい問題だと言ったけど,そういう問題よりも難しい問題がある.要するに多項式時間で検証できないような問題が存在するということ.そういったNP完全な問題と同等か,それ以上に難しい問題をNP困難という.NP困難はNPってついてるけど,必ずしもクラスNPに属してるわけじゃない.NP完全より(以上)は難しいという意味.

部分和問題の話の中で,この問題はNP完全だという話をした.この問題はNPには属していそうだけれど,Pには属してなさそうな感じがするかもしれない.しかし残念ながら,部分和問題は多項式時間で解けるかどうかはわかってない.もっというとPとNPが同じかどうかはミレニアム問題という多額の賞金が出る問題となっていて,今現在も全力を上げて研究者が調べてる.なので,P=NPかP≠NPのどっちであるのかわからないけれど,計算機科学を取り扱ってる多くの人の見解は,同じではないだろうということで一致してるのだと思う(おそらく).

誰か頭のいい人証明して~

内容についてどう思いますか?
  • いいね (6)
  • だめ (2)

やりたいこと

やりたいと思っていることがいくつかある.箇条書きにすると

  • FPGAのCPU実装をもっと頑張る(具体的にはUnix系OSを動かす)
  • Rustをやる(できれば研究とかバイトのコードも徐々に移行したい)
  • 日本語力を上げる
  • もっといろんなことを勉強する(暗号,音声,機械学習,etc)

のような感じ.別に最後のやつは普段のタスクの中に自然と組み込まれている感じなのであまり意識する必要はないだろうけど,上から2つは個人的に時間を作ってやらないとできるとは思えない.3つ目は文章が下手くそなのでうまくなりたいなということ(願望).

FPGAのやつはできればCPUの実装のコード(verilog)をきれいにしたというのもある.研修Aという研究室の自由課題でやったものだから,締切に合わせて結構その場しのぎでやってしまった感があって,それをどうにかしないと次に進む上で障害になりそう.かと言ってあれってそんな簡単に直せるとは思えない… 抜本的に書き直す羽目になりそう.そもそもverilogってアセンブリに近いものがあって全然きれいに書けてる自信がわかないんだけどどうすりゃいいんだろう.高位合成とかと違って結構低レイヤだから記述量が多くなりがちなのが影響して,とてもじゃないけど見やすくならない.あれも結局経験値で決まってくるやつなんだろうな.

Rustについて言えば,とにかく実践で使っていくしかないだろうなって思ってる.入門書とか初心者向けの記事とかをただ追って読んでるだけだと全然頭に入ってこないたちなので,実際に使って鍛えていくしかない.自分もそんなに詳しいわけじゃないんであれだけど,c言語とかc++みたいなシステム周りとか結構低いレイヤのプログラミング言語って,D言語とか他にもあるんだろうけど結局のところc言語 or C++がデファクトスタンダードって感じがあるように思う(マイコンとかの開発環境でC++/C以外の言語を使う場面ってなくはないけど少ない気がする).LLだとか関数型言語とかだと選択肢がありすぎるくらいにはあるのに,低レイヤ向けの,アセンブリより抽象度が一つ上なメジャーな高級言語ってのが,もう何十年も前に発明されたCとかC++のまま変わってないってのは,あまりに時代遅れな感じがする.と言いながらもう10年近くCだとかC++を書いてきた人間がこんなことを言うのは説得力にかけるのかもしれないけど,流石に限界というかこのあたりにもイノベーションがあってもいいよねってのは薄々思っていたところ.確かにC++は最近になってC++14とかC++17とか新しくなってきてるけど,もともと難解だったC++に更に付け足しつけたしで色々くっつけたもんだから複雑怪奇になって来てて,「C++を理解してます」ってのがジョークになるという笑うにも笑えない状態になってる.

だから流石にそろそろ新しくそういうシステム周りもかける言語を習得したいなと思ってたわけだけど,ちょうどMozillaがRustを開発してるという話を知って,これは良さそうと感じた.最近はライブラリも結構充実してきてて特に問題もなさそう.他に最近話題のコンパイルするような静的型付け言語としてはGoとかもあるけど,あれはポインタを叩くような処理をするというよりは,コンパイルできるLLみたいなイメージが有る.Google的には速度が出るLLが作りたかったってことなんかなという印象(素人目線).個人的にはやっぱりLLとシステム記述向けの言語って住み分けができてると思ってて,前者が簡単にかける代わりに詳細な記述をしたり速度を出したりすることが難しいもので,後者がその反対という感じ.よくGoとRustを対比させる記事を見るけど,それはこの2つがちょうどLLとシステム記述向け言語の間くらいに位置する言語だからということなんだろうな.ただGoはどちらかと言えばLL寄りで,Rustがシステム記述向けよりなんだろうと思うし,だからこの2つは用途が衝突するところもあるけど,全くかぶらないところもあるんだと思ってる.

確かにLLって半端じゃないくらいに遅いから早くしたいと思う人が多いのは当然だよね.pythonくらいしか経験がないけど,それでもC++なら一瞬で終わる処理が半端じゃないくらいに時間かかったりするのを見て,何とも言えない感じなることはある.プログラミング界隈で有名な話?に80:20則ってのがあって,プログラム全体の20%が実行時間の80%を占めてるって経験則なんだけれど,LLの哲学的には,重い20%のコードをCとかにまかせて,速度がでなくても大丈夫な80%ところをLLでどうにかするって話だったんだと思う.確かにそれは合理的に見えるし,全部を無駄に書くのが大変な言語で修行のごとく記述していくのは意味がないってのは大いに賛同するところなんだけど,現実はやっぱりなかなか厳しいものがあって,そう簡単じゃない.実際に使ってみると,LLがおそくてその80%が馬鹿みたいに大きくなったりして,僕の書き方が悪いってのはあるんだろうけど,なんだかなーって結果になることも往々にしてある.そんなこんなあって,みんな早いLLを求めてたんだろうから,Goみたいな言語が出て来たんだろうなという予想.本当のところどういうことなのかはGoを勉強しないとわからないけど,今のところGoが重要そうなWeb界隈の方には全く関わりがないので,実用的な観点でやることはなさそう.

とまあ前置きが長くなったけどRustを勉強したいなと思ってる.関数型言語の流れを受けて色々と拡張があるみたいだし,加えてC++とかと比べて安全だと言われればやらない理由も特にない.速度も結構早いみたいだしね.

ということで今年度も頑張っていきたいと思います.

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)