https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @nico_shindannin 「２部グラフの最大マッチング」は「最大流」に帰着させたら解ける、みたいなのあるじゃないですか。ということはある意味、2部グラフのマッチングは最大流より簡単な問題だと言える。みたいな関係を考えたときに、「どんなNP問題もハミルトン閉路に帰着できる」 | |
| @nico_shindannin という恐るべき事実が知られているので、ハミルトン閉路ってめっちゃ難しいんだなあしみじみ、というのが「NP困難」とかの"○○困難"という用語です。PとかNPは最強アルゴリズムで解いた時の計算量の話で、"完全"や"困難"はそこから派生する感じの性質 | |
| @nico_shindannin そうです＞上下関係。出力フォーマットというのは、たとえばハミルトン閉路だと、「グラフにハミ(略)路があるか判定してYES/NOを返せ」という問題だと答え作る側もハミルトン閉路解かないといけないので大変ですが | |
| @nico_shindannin 「グラフのハミ路をvector<int>で返せ(複数あるときはどれを返してもいいよ)」という出力形式にしてあれば、答えが正しいかのチェックはO(n)でできます。という雰囲気で、うまくチェックが楽そうな形式に一般化したら多項式時間で検査できるがNP | |
| NPの、本来の意味での定義は「非決定性チューリングマシンなら多項式時間でyesが返せる」で、答えが正しいかのチェックが云々、というのは、まあ結果的にだいたい同じ意味になるので、そっちで説明しちゃってるだけで、というかそっちの方が適当に説明しやすいのでつい流れているだけで、 | |
| 間違えなくちゃんと理解しようと思うと非決定性計算を把握した方がいいと思うます。やっぱりフォーマルにならないように説明しようとすると端々がいろいろ怪しい。 | |
| @WtbH NP完全 = NP(答え合わせできる) かつ NP困難(どのNP問題も帰着できる) です。 | |
| NP困難だがNPではない（従ってNP完全でもない）問題の例： 「C++のソースコードを入力文字列として受け取って、それをコンパイルして実行したら何が出力されるか求めよ」 | |
| @nico_shindannin そんな感じです。 | |
| 非決定性チューリングマシンでコード書く機会があれば、この辺みんな一発で頭になじむと思うんですよ。NTopCoderというサイトを立ちあげ、提出されたコードは非決定性TMでO(n^2)で動けばAccepted、O(n^3)ならアウト、みたいなNSRMという大会を毎週開く必要がある | |
| @nushio はい、ほとんどの問題をエンコードできるのでNP困難です。NPやNP完全などという簡単すぎる計算量クラスにはとても収まりません。 | |
| @nushio Yes. http://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3 Wikipedia のこの図は一目でわかりやすいと思います | |
| @izumi_yusuke そうそう、マルチテープならまだいいけど、シングルテープだと脳内言語ではどう考えても線形時間のアルゴリズムが二乗オーダになったりしてあれはかなり大変だ。 | |
| 「素数判定はNP」を自力証明してみると、NPてのがどんな難問も含まれるバカデカい計算量クラスでは決してなくて、そんなことは決してなくて、難問の多項式時間解法を考えるのが難しいのと同じく、メチャメチャな難問はNPでも決して解けず、解ける問題でも色々工夫が楽しいというのがよくわかる | |
| あと NP と co-NP の違いがよくわかる。 | |
| PやNPの上にも下にも色々な話があって、ここで問題 『入力：(ノード数Nの無向グラフ, 頂点u, 頂点v) 出力：uとvがconnectedかどうか判定せよ。「ただしメモリを O(log N) しか使っちゃダメ」』 が解けると2009年のゲーデル賞らしいですよとか。 | |
| http://cstheory.stackexchange.com/questions/4053/sum-of-square-roots-hard-problems 計算量クラス全然よくわかってない系男子：『BigIntが2n個与えられます。Σ_{i=1～n}√a[i]とΣ_{i=n+1～2n}√b[i]どっちが大きい？』 NPより上と思われているPSPACEには入るのはなんとかわかってる、位に意外と | |
| 難しいんだけど、かといってNP困難と証明されているわけでもないので、意外と実はPで解けちゃったりするのかもみたいな状態の未解決もんだい。 | |
| @ikegami__ 僕が！全力で！ P∩NP＝φ ではなく P⊆NP だから、という話をしているのに！（日本語訳：おはようございます）。もちろん「AKSにより素数判定はP」「P⊆NP」「よって素数判定はNP」という三段論法で証明してもいいですけどそれ自力証明とかまず無理… | |
| .@fukutax さんの「DEIM2011 初日」をお気に入りにしました。 http://togetter.com/li/106168 | |
| およよ @salmonsnare さんが ∩(._.)∩ | |
| @cpp_akira 「1を読んだら2と3も必ず読みたくなったアキラさんが手元に全巻買い揃えたところで僕が読ませてもらう作戦」をもくろんでいます。よろしくお願いします！ | |
| #konronkai http://partake.in/events/446f5a7b-9a65-4c3a-b917-8138099c6a61 会場設営しました。記念カキコなどしたい人はどうぞ。あとそういえば、当日は日曜日ですので「普段大学のネットワークからなら読めるジャーナルなのに、しまった！」ということがないように、お目当ての論文がある人はお気を付けて | |
| Goodbye Lullaby http://www.amazon.co.jp/dp/B004IXD3ZO 届いてた！取り込み中。久しぶりのAvrilだ。楽しみ |