私は、一生、学生扱いで終わるんだろうなあ、きっとｗ

P=NP?問題の覚え書きのこれからの進め方という原稿を一応書きました。しかしながら、実は、再開するかどうかを迷っています。というのも、ここからが更に内容も難しくなります。また、Cookの定理までがテキストいえば一五ページまでです。これに隔日で書いても三ヶ月ほど掛かった記憶があります。これから、テキストで言えばあと九〇ページほど紹介するつもりですが、つまり、週に一度ぐらいのペースでやっていれば、この問題の説明には下手すると一生掛かってやるという事になるかもしれないという覚悟が必要です。

どうしようかな、と真剣に考えています。

とりあえずですね、原稿は書きためようと思いますが、アップはしないつもりです。少し見えないところで原稿を進行させて、進行の具合を考えてみたい。試行錯誤という奴です。

そういうわけでどうかご理解をお願いいたします。

P=NP?問題の証明のもっとも肝心な部分についての考察

私の知っている範囲で言うとP=NP?問題では全て肯定的なリラテル（論理式の最小単位）の場合P=NPであることが証明されています。

残る問題は否定のリラテルがあった場合、計算量を減少させられる事が知られていますが、それがどれくらいの影響があるかと言うことでしょう。

そこで考えたことを、以前mixiの日記にメモ書き程度に残したことをここに公表したいと思います。ちなみにRotaTRはわたしのIDです。


否定のリテラルによって減少する計算量は０　2010年09月28日14:29
SATに於いて計算量を減らせるのは、
あるブール変数以外がまったく同じ場合

節集合Ｃの各節はブール変数の論理和で表されるが
そこに表されていないブール変数の値はＦとしてよい。

従って各節はブール変数の二つのリテラルとＦの３つの値を取り得る。

ブール変数の集合Uがm個のブール変数を持ち、ｍが十分大きいとする。
また、節集合の元の個数ｒとする

このときある節が節集合Ｃに現れる確率はｒ/3^m
それと対になり消滅する節が同じ節集合に現れる確率もほぼ同じ

一方それによって少なくなるＴＭの計算量はO（r/2）

従って、mが十分大きいとき否定のリテラルによって減少する計算量は０
コメント
コメント

RotaTR2010年09月28日 14:41

> SATに於いて計算量を減らせるのは、
> あるブール変数以外がまったく同じ場合
> 説集合Ｃの各節はブール変数の論理和で表されるが
> そこに表されていないブール変数の値はＦとしてよい。
> 従って各節はブール変数の二つのリラテルとＦの３つの値を取り得る。
> ブール変数の集合Uがm個のブール変数を持ち、ｍが十分大きいとする。
> また、節集合の元の個数ｒとする
> このときある節が節集合Ｃに現れる確率はｒ/3^m
> それと対になり消滅する節が同じ節集合に現れる確率もほぼ同じ
> 一方それによって少なくなるＴＭの計算量はO（r/2）
> 従って、mが十分大きいとき否定のリラテルによって減少する計算量は０

少なくなる計算量は平均でｍ／２の定数倍が正しいです。
お詫びして訂正いたします

RotaTR2010年09月28日 19:45
リラテル＝＞リテラル
説集合＝＞節集合

と修正

RotaTR2010年09月29日 03:45
しまった。いろいろ間違ってる。

｛｛a,b｝,{a,NOT(b)}={a}

だｗ

まぁ、こんな感じで減らせるんでしょう。
節の出現確率のところだけは使えるな（笑い）

RotaTR2010年09月29日 03:50
情けないなぁ、まったく

補足しておくと、{{a,b,c},{a,b,NOT(c)}}={{a,b}}

まぁ、減らせる計算量は同じだけど、更に減らせる可能性があるよね

RotaTR2010年09月29日 03:52
{{a,b,c},{a,b,NOT(c)},{a,NOT(b})}
={{a,b},{a,NOT(b)}}
={{a,b},{a,NOT(b)}}
={{a}}

とかね。

RotaTR2010年09月29日 03:55
あ、しかし、そういう節の出現確率も上記の出現確率だから、良いのか。
あははｗ

ま、まぁ、出先でのメモということで許して下さい。
いろいろと検討が足りなくてすいません。

RotaTR2010年09月29日 04:10
しかし、ごくまれだと思うけど、


{{a,b,c},{a,b,NOT(c)},{a,NOT(b})}
={{a,b},{a,NOT(b)}}
={{a,b},{a,NOT(b)}}
={{a}}

の例のように計算するブール変数の量が減らせるときは、計算量は著しく減る場合もあるね。そこの変まできっちりと計算する必要があるのかな。ないと思ってたけど、検討すべきですか？うーん、ちゃんとすべきかもね。そこ変が残る課題か。

RotaTR2010年09月29日 04:19
あ、いいか。そういえば、昼に頭の中で検討したときには、パターンは出現確率がｒ／３^mに対し、そのようなパターンで削減される計算量はO(2^m)なので、削減量は確率を考えると、最大でO(２＾ｍ/３＾ｍ)なはずで、ｍが大きくなると、０に近づくと考えたのだけど、大丈夫だよね？

RotaTR2010年09月29日 04:20
なんか、本当にいろいろダメだなぁ（苦笑）

少し昔話をしよう

パーセプトロンやP=NP？のブログをやらないことでいろいろいわれるようになった。

ところで、ちょっと前のmixiの日記を見たらこういうことを書いていた。なんでもそうだけど、某とかが私のやることにくちばしを突っ込んでは、要らんことばかり言われていた一つの証拠をお見せしたい。

ちなみに、P=NP問題に関して私なりの解答は考えたのでそれは後ほど公表したい

（以下その日記）

P=NP？問題を考えてみたい理由　2009年05月27日19:11

私は、残念ながらお金にはならなかったが、
動画の超解像技術の元になったアルゴリズムや、
その他、クラスNPと思われる問題の解決に於いて
いくつかのヒューリスティックアルゴリズムを考え出した
実績がある。


また、非線形な問題を考えるときには、ある種の変換を持って
線形な問題として解くともあれば、シミュレーションによって
最適解を得ようとする場合もある。

私の場合、人工知能の研究などでしばしば、
ヒューリスティックアルゴリズムを持って解決するということが多い。

一体、ヒューリスティックアルゴリズムという問題解決方法
一種の知識は、ただの試行錯誤の結果なのか？
そもそも、問題を解決するとはなんなのか？

その根本はどこから来るのか？という意味でP=NP？問題は
大変に興味深い。

非線形がある種の経験論、言い換えれば、経験の知識の組み合わせで
あるかもしれないのに対して、
つまりは、非線形性を線形に置き換えて解くか、
経験というデーターベースによるシミュレーションによって
最適解を探すか、ということに置き換えられる可能性が高いのに対し
NP問題に何らかの解決をもたらそうとする
ヒューリスティックアルゴリズムは経験上全く別種のものである
ということが言える。

それは、ヒューリスティックアルゴリズムは、アルゴリズムというように
何らかのアルゴリズムがあるからである。

精神の一部がヒューリスティックアルゴリズムの集合であるということは
否めない。それは、我々の感性が教育によって共有されることからも判る。

そういうわけで、P=NP?問題は私には非常に興味深い問題なのである。

だから、あまりうるさく言わないように。