tw.log

https://twitter.com/kinaba のログ (twilog の方が便利です。)

20140930 23:26	http://www.lmcs-online.org/ojs/viewarticle.php?id=1207&layout=abstract 読んだ。[∃SO(二階述語論理ただし二階量化は式の頭で∃しか使わない)論理式]かつ[∀FO(同様)論理式]、の形に書ける問題がNP完全(※)なら、"かつ"の左単体もNP完全。つまり単純な記述言語での条件追加では問題が激しく難化はしない

presented by k.inaba (kiki .a.t. kmonos.net) under