  |
はてなキーワード: NP完全とは
P対NP問題は、計算複雑性理論における中心的な未解決問題であり、計算可能性と効率性の境界を探るものである。この問題は、計算モデルの深い理解と数学的厳密さを要し、多くの研究者が取り組んでいる。
NP完全問題は、NPクラス内で特に重要な役割を果たす。問題 L がNP完全であるためには、以下の条件を満たす必要がある：
1. L がNPに属する。
2. NPに属する任意の問題 L' が多項式時間で L に帰着可能である。
クック・レヴィンの定理により、最初に証明されたNP完全問題はサティスフィアビリティ問題（SAT）である。この定理は、任意のNP問題がSATに多項式時間で帰着可能であることを示している。
P対NP問題は、P = NPかP ≠ NPかを問うものである。
もしP = NPが証明されれば、NP完全問題を含むすべてのNP問題に対して効率的な（多項式時間の）解法が存在することになる。
逆に、P ≠ NPが証明されれば、NP完全問題には効率的な解法が存在しないことが示される。
この問題の証明は、いくつかの既存の手法では限界があることが知られている：
P対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完全という情報にぶちあたって絶望してしまい、勢い余って変なものを書いてしまった。
────
実際の多くの人狼プレイにおいては、こうやって必死に狼を探そうとしても、勝利をもぎ取っていくのは第三勢力の狐が多いというオチがつく。
