■PvsNP(P!=NP)問題の別解（らしきもの）

一部の人には有名なPvsNP(P!=NP)問題の別解をhttp://arxiv.org/abs/1008.2247でまとめたのですが、twitter弄っていたらなんかまとまったのでこちらにも転載しておきます。

誰か突っ込みをお願いします。

まずチューリングマシン(TM)の大きな特徴を考えます。TMの計算力の源として「複数ある入力をまとめていくつかの計算結果にする」というものがあります。

例えば足し算 1+2+3+4+5 は、あらかじめ定められた計算によって15という計算結果となります。 10+5, 1+14, 5+5+5 なんかも同様ですね。これらの入力も結局は15という計算結果にまとめられます。

もちろん、人間の別の入力やランダムを活用すれば何とかなりますが、基本は入力だけに依存するという条件になりますので、入力が同じならば結果も同じになります。

「複数ある入力をまとめる」というのがTMの特徴だとすると、その入力同士の関係はどのようになっているのか？というのが http://arxiv.org/abs/1008.2247 の骨子です。

TMの入力と出力の関係が簡単であればあるほど、計算する時間も短くて済みそうです。逆に入力と出力の関係が複雑であればあるほど、逆に計算する時間が長くなるでしょう。

では、TM計算量と入力／出力の関係はどういうものがあるのか？

関係を扱う数学の道具はたくさんありますが、ここで私は大好きな対称性を使ってみました。

複数の入力をまとめる時、決定性TMでは高々1つの文字しか変更することができません。計算途中のテープの文字は一致している必要があります。

しかし、入力／出力の関係が複雑だと、これをまとめあげるのに多大な苦労があります。気を付けないと、間違った入力まで一緒にしてしまう可能性があります。

そこで、http://arxiv.org/abs/1008.2247 で一つ仮説を立てました。 「テープ全体を使って、テープの変更する場所＆文字を1ヶ所以上決定できる」 この関係が常に成り立つのがPではないかと。

HornSATやCNFSATをベースに色々と弄ってみたところ、ビンゴ。あたりのようです。このような問題を秩序問題と名付けました。

秩序問題が来れば今度は混沌問題でしょう。ということで混沌問題を定義して対比させます。

秩序問題は下記の通り「計算結果が対称となる1文字を活用して虱潰しに可能性を制限することができる」という特徴があります。

ならば、混沌問題は「複数の文字がセットでないと計算結果が対称にならない」ということでしょう。この複数の文字を拡張文字と名付けます。

こちらもビンゴ。あたりです。CNFSATやSATでは、拡張文字の長さに上限がありません。つまり、拡張文字は無数にあることがわかりました。

それでは、拡張文字とは何でしょう？ 「0,1,2……を使った数の表記みたいなもの」です。文字を組合せて使うことで、その部品だけでは表現できなかったたくさんのことを表現する文字です。

秩序問題にはこの拡張文字のような「一つに固まった塊」「どこまでも増えていく塊」という概念はありません。結局文字一つ一つをバラバラに扱えますので、塊として扱う必要がありません。

そして、拡張文字は、長さのべき乗規模で数が増えていきます。 ……ここで「指数規模」というPvsNPに繋がるギャップが出て来ました。

ここまで来ればあと一息です。

秩序問題と混沌問題の違いを浮き彫りにします。 まず、NP完全の混沌問題はP完全の秩序問題そのものでは表現できません。そして、指数規模に膨れ上がった拡張文字のせいで、秩序問題を多項式規模で繋げても混沌問題を計算することはできません。

よって、P(秩序問題=P完全) << 混沌問題=NP完全 となるので、PvsNPはP!=NPとなります。

……という話をhttp://arxiv.org/abs/1008.2247 にまとめています。 誰かコメント貰えると助かります。 もう自分じゃギャップ見付かりません…………

http://arxiv.org/abs/1008.2247 の日本語ファイルはhttp://arxiv.org/e-print/1008.2247v4 にあります。拡張子を.tar.gzに変更して展開して下さい。

Permalink | 記事への反応(1) | 17:27

ツイートシェア