例として、ナップサック問題と部分和問題を取り上げる。cn}Cが与えられる。im}の選び方を求める。xiとし、ナップサック問題を解く。最大値がCならば、部分和でyが構成できる。最大値がC以下ならば、部分和でyが構成出来ない。いう手順で、部分和問題がナップサック問題へ変換できそうだ。問題の変換は、O(n)なので、TMを用いて多項式時間でできる。部分和問題は、ナップサック問題へ多項式時間チューリング還元可能。ここまでやると「NP-hard」の定義の意味が分かった。やって見ると、問題Lは問題Hの特殊形であることが分かる。問題Hが一般形の問題なので、問題Hは問題Lと同等以上に難しいという点についても納得がいく。ここでNP-hardはクラスNPの部分集合と誤解されがちだが、これは間違い。NP-hardの問題は、必ずしもクラスNPに属さなくてもよい。それじゃ、次にNP-completeの定義を見てみる。うーん、つまりNP-completeは判定問題でなければならないと。先ほどのNP-hardの例から分かるように、NP-completeは、すべてのNPクラスの問題の一般系と考えられる。そんな超汎用的なNP-completeは、当然NPクラスの中で一番難しいはずである。アバウトな議論なので、数学的に証明してみます。NP-completeより難しい、クラスNPの問題hが存在すると仮定する。定義より、NP-completeな問題を解くことで、問題hを解くことができる。これは問題hがNP-copmpleteより難しいという仮定に矛盾。よって、NP-completeはクラスNPで一番難しい。□なんか、分かってきた気がする。最後にwikipediaのベン図を見て、いろいろ考察する。P!=NP予想の関係により2種類のベン図が書かれています。これはちょっと式を書けば分かる。(厳密な数学的証明にはなってない気はするけど。NP-completeより、P(=NP)に含まれる問題はすべてNP-complete。□なんか、すっきりしたー。気になることが出てきた。動的計画と擬多項式時間について次のブログに書きます。Postsmemset()とmemcpy()恥ずかしながら、Cのmemset()とmemcpy()を今まで使ったことがなかった。みたいな話を聞いたことがあったので、「あーじゃ要らない機能なんだー。editorialに投稿された解答がmems...便利なPythonライブラリ(5)retryデコレータつけるだけで、リトライしてくれるという便利ライブラリ。失敗するかもしれない不安定な関数に@retryをつけると成功するまで実行してくれる。ret...S3のファイルを一般公開するAWSのS3のファイルを一般公開する方法について説明します。2つの場合に分けて説明します。本番中ゴリ押し解を思いつくには思いついたのだが、C++でマルチスレッドの処理を書いたことが無くて、ごにょごにょやってるうちにタイムアップとなってしまった。C++...C#入門(9)Action、Func、Predicateの違いAction、Func、Predicateについて簡単に整理しておく。メソッドへのDelegate。メソッドへのDelegate。スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。「スライド区間」の定義ですが、窓関数のようなものを想像してください。まではコンピュータの力を使って正多面体をt色以下で塗るパターン数を数えていました。今回は手計算で計算してみようと思います。そのためにはまず回転を表す対称群をうまく列挙するために回転軸について考える必要があります。見聞きする木の用語を整理しておく。節点vから最も離れた節点をwとする。w)の長さをvの離心数と呼ぶ。記号で表すときは、ε(v)と書く。使って遊んでみました。いった便利な機能を提供してくれるテストフレームワークです。repor...キャッシュヒット率の測定perfというツールを使ってキャッシュヒット率を測定してみた。キャッシュの影響なんてたかが知れていると甘くみていたら、痛い目るので要注意。知らない用語がちらほらあったので、簡単にまとめておく。