https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @eomole ボタンポチポチ押してれば誰でも自動でアップロードできるので、「arXivに置いてある」というだけでは、中身の信憑性は 「どっかのアプロダに置いてあって2chにリンク貼られてた」 と変わりないです。 | |
| 風呂った。みんな納得してるみたいだけどしかし、少なくとも ∃*∀*(任意のbool式) の評価がNPでできたら普通に十分すごいので、(1)∃*∀*3CNF 程度なら特にすごくない (2)まださらにどっか間違いがある、のどちらであるか指摘されてないと安心して寝れなくないんですか皆様 | |
| @xhl ∀*(任意のbool式)=1 の判定問題が既にcoNP完全なので、これがSATに多項式時間還元できるとNP=coNPとなっちゃって、事件であります。 ∃∀CNFに限ると（∃DNFのSATisfiabilityが自明に解けるのと同じ理由で）簡単になる、というのが僕の認識。 | |
| megatokyo 6 読んだ。やっぱりまとめて読むと印象違うなあ。密度濃い。この、一コマで２つも３つも別ラインのストーリーに属する会話を錯綜させながらまとめていく描き方はけっこうこのマンガ独特な気がするんだけど、不思議とすんなり読めて楽しい | |
| @xhl CNFの恒真性判定はPですが、任意のbool式の恒真性判定はcoNP完全です。 | |
| @xhl あ、はい、そういう意図でした。どうもわかりにくくてすみません | |
| この感じ…定期「P=PolyTime、NP=NotPolyTime と誤解する人が多いので N がNondeterministicの略と強調するために P の方を DP=DeterministicPolyTime と表す習慣を作って余計に別の物と紛らわしくしようぜ」タイムか…！ | |
| http://d.hatena.ne.jp/camlspotter/20100714/1279072171 高階性もそうかもですが、多相性が難しさを増してるのでは、という気がしてました。4つのtwiceが全部型が違うのは（でも問題なく型チェック通る…のは当然なんですけど）不思議 | |
| でも[a]→aを一つの式中で[int]→intと[bool]→boolと[[int]]→[int]に使い分けるのは別に怖くないから、aに入る型のorderがころころ変わる（= 激しく高階関数が入る）方が本質的なのかなあ。あるいは[[int]]→[int]は少し怖いので構成子の階数 | |
| 先ほど、「当たり前」と書いたら140文字オーバーしたので、２文字減らそうと「当前（とうぜん）」にしてて、ポスト寸前に慌てて踏みとどまって「当然」に直すなどのドラマがありました。 | |
| @hogelog http://twilog.org/kinaba の方が明らかに便利なので自分でもそっちしか使ってないんですが、しかし自分の発言ログを他のサービスに預けっぱなしとかないわーと思ったので、念のため自分でもクロールしております。そいえばbit.lyの展開も実装せねば | |
| て、今気づいたんですがなんで僕は twilog さんにprotected扱いされてるのだ？？？ http://twilog.org/kinaba | |
| なおった | |
| @oxy こんなフィードが。知りませんでした。ありがとうございます。CoRRのpreprintの概要全部眺めるのはS/N比考えると辛いかなあと思ったんですが、この程度の流量でタイトル見るだけなら行けるかな | |
| @tokoroten 名前だけ見て http://www.hugeurl.com/ と同種のサービスかと思ったら、マトモな感じでした…！ありがとうございます。便利そう | |
| @oxy 読みます！Constant-Time Approximation の話はいつもoxyさんの論文を足がかりに勉強させていただいてます | |
| 自分は一本だけ http://arxiv.org/abs/0910.2315 CoRRに置かせてもらってました。共著者の「PLAN-Xの会議録をDBLPが回収してくれなくなったけど不思議なことにarxivなら拾ってくれるから上げとこうぜ」という提案による。 | |
| 中身は一発ネタというかTopCoderのSRMに出したら500点問題くらいじゃないですかと思っている | |
| @oxy いえ、少なくとも今のところは100%僕の趣味です。形式言語というかオートマトンの性質検査の方面で、そういう話に持って行けたら面白いなーということは思っているんですが、具体例はまだ僕の中にはないですね | |
| Nonstrict memoization http://conal.net/blog/posts/nonstrict-memoization/ 読んでる。「メモ化のために表引きしようとすると非正格(lazy)だった関数が正格になっちゃいますよどうするの？」 問題。たのしい。 | |
| 実装は結局 http://hackage.haskell.org/packages/archive/unamb/0.2.2/doc/html/src/Data-Unamb.html#unamb こういうことになるのだが restartingUnsafePerformIO てヤバい | |
| FEのこの前DSで出たリメイクは暗黒竜だけだったんだ…ということを紋章の謎のリメイクが出るというニュースを聞いて初めて認識した |