https://twitter.com/kinaba のログ (twilog の方が便利です。)
| "login with facebook"が動かなくて例の論文ダウンロードできない…。7章の頭ずっと読んでたのだけどやっぱ最初からというかこの方の昔の研究から読まないとよくわからんな。R_pの定義が他の部分みないと謎だ。 | |
| 「1: FO(LFP)が多項式時間と一致するような構造の上にSATをエンコードします」 「2: FO(LFP)論理式を充足するような構造の分布として可能な分布は、SATisfiableな式をエンコードした結果できる構造の分布と一致しないことを示します」 おわり、と多分言っている。 | |
| まあ僕はrandomとかstatisticsとか使った証明は全然読めない人なのでこれは納得する方向にも反証する方向にも歯が立たない気がする…。通信路符号化定理のrandom coding使った証明とかですらいまだに自信がないレベル | |
| 記述計算量 http://en.wikipedia.org/wiki/Descriptive_complexity という分野があって、例えば「"∃SO"という言語で書き下せる問題は必ずNPで解けます。しかも逆に、NPで解ける問題は必ず"∃SO"で書けます」みたいな定理を示したり、そういう∃SOみたいな計算量と綺麗に対応する論理を考える分野 | |
| FO(LFP)というのは普通の論理式で使うand,or,not,∀,∃に加えて（制限された形の）再帰も使ってOKという論理体系。これで書ける問題は（扱うデータに全順序が入ってる(C++でいうと全ポインタを<で比較するのが許されてる感じ)時なら）Pと一致するという古典的な定理がある | |
| ぬぬぬ80文字くらいで余裕で完璧に説明できるだろうと思ったら全然甘かったし結局まったく意味の分からん説明になってしまった…。自分自身がちゃんと理解できていない証拠である | |
| @tri_iro @qnighy 月一は言い過ぎってほどでもない気がします。 http://www.win.tue.nl/~gwoegi/P-versus-NP.htm で捕捉されてるだけで2ヶ月に1本くらいは… | |
| 大事なことを書き忘れていた。道を歩いてたらセブンイレブンの張り紙で "あま～いトマトゼリー" http://www.711net.jp/product/n/a01a07/g/407031000000000/p/9510082 なる存在を知ったので買ってみたらおいしかった。おすすめ | |
| そうか！どっかで聞いた単語だと思ったら http://serif.hatelabo.jp/a2504c7ccb748c24565b1feb73f6bf2192e81383/5dc106963ea615a0fadb98e1120bf79605cecf97 これだった！ RT @Cryolite: http://www.scribd.com/doc/35539144/pnp12pt なんか "Random Fields" とかいった見慣れた... | |
| CAA (Computer Applications (略) in Archaeology) http://www.caa2010.org/ という会議があるのかー (via http://togetter.com/li/40760 ) 面白そう | |
| PPL2011 http://www.info.kochi-tech.ac.jp/ppl2011/ のページができてました。札幌だそうです。プログラム委員会のメンバー見たときにわりと同年代が多くてびっくりした | |
| P≠NP論文いちおう通して読んだ(detailは理解してない)けど、この論文のoriginalの部分(Chapter4の最後とChapter7)になると自然言語率があがりすぎて読めない…もっとformalに書いて下さい、っていう感じが。完成版を待たないとなんとも言い難い気がする |