  |
はてなキーワード: NP完全とは
量子コンピューターが実現されてしばらく経った。
それを開発したチームはとてもクローズドで彼らとの接触もままならないほどだった。NP完全な問題にもアクセスすることができるのも、結局彼らだけだった。
彼らは、技術、考え方、ファッション、全てにおいて、違う価値観を持っていた。私たちにとって、まるで未来人のように見えた。
同じ人間だったが、まるで違う生き物に思え、その他人類が初めて劣等生物だと認識さえしそうだった。
ただ、大学のO先生は彼らと接触できた。今まで通算1000回は接触し、日本人として初めての功績(もはや接触するだけで功績になる)をあげ、新聞にも取り上げられていた。
O先生は、「彼らだって、私らと根本は同じなんだよ」そう言っていた。
私は指輪を失くした。場所を探すためには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に変更して展開して下さい。
人狼というゲームがある。カンタンにいえば、集団内の秘密組織工作員を排除するゲームである。
たいていは工作員を炙り出す役職なども存在し、それによって直接・間接にもたらされる情報がゲームを左右するのだが、まずは単純なモデルを考えてみたい。a人の集団A1, A2, ..., Aa内に、互いに顔見知りのb人の工作員B1, B2, ..., Bbが潜伏していて、a人全員がそれぞれに排除すべき人物を記名投票している。aとbの数は全員が知っている。投票数を最も集めた人物から排除されてゆく決まりがある。そして、他には何も情報がない状況である。
単純に考えれば、b人の工作員はお互いが排除されないよう、身内には投票などしない。そこでa人からなる完全グラフをまず描き、投票関係に陥ったエッジを消してゆくことによって得られるグラフGのクリーク問題は、工作員を推定するのに使えるのではないだろうか。
集団のとある人物Aは工作員なのだろうか？グラフGにおけるA1を含むエッジ数bのクリークはC(A1)通りだったとする （あるいはC(G,b,A1)と表すすべきかもしれないが…）。C(A1), C(A2), ... , C(Aa)などと計算してゆき、さらに、その最大値を取る人物を探す。Jだったとしよう。はたしてJはどの程度工作員なのだろうか？何らかの妥当な仮定を置くと、Jが工作員である確率がC(A1)～C(Aa)やbなどから計算できるのだろうか？
身内投票の可能性を考えると、事態はより混沌となってゆく。つまり、C(A1)～C(Aa)に比べて十分にC(B1)～C(Bb)の値を小さくしながら、かつ、工作員の誰もが最多票をもらう確率を十分に抑えることが可能な、何らかの戦略が存在しうるのだろうか？
────
クリーク数を求める高速なアルゴリズムがないか探そうとしたら、すぐさまNP完全という情報にぶちあたって絶望してしまい、勢い余って変なものを書いてしまった。
────
実際の多くの人狼プレイにおいては、こうやって必死に狼を探そうとしても、勝利をもぎ取っていくのは第三勢力の狐が多いというオチがつく。
