https://twitter.com/kinaba のログ (twilog の方が便利です。)
| The Simplex Algorithm is NP-mighty http://arxiv.org/abs/1311.5935 ちょい面白かた。NP完全問題のインスタンスをグラフの最小費用流問題(のLP表現)にエンコード！し、単体法走らせたら特定の辺が基底に入る⇔元問題の解がyesとできる | |
| 続) https://t.co/s66q0U3MSc つまり、単体法は線形計画問題という多項式時間で解けるものを解こうとして、実は密かについうっかり密かにNP完全問題が解けるほどパワフルな計算をしちゃってる（ので最悪指数時間かかってしまうのも頷ける）のだ…！！！！というお話し | |
| あ、さっきのは SODA 2015 の accepted papers http://www.siam.org/meetings/da15/da15_accepted.pdf にあったやつです（みなさま色々読んで僕に解説してください） | |
| @eomole しかし構成を見ると、既知の指数時間かかるインスタンスを使えば指数個のメモリ状態を作れるのでNP完全問題に対する解候補全列挙相当の処理は自明に表現できて、あと巧妙なガジェットで候補のyes/no判定(in P)も埋めれるという作りなのでさほど凄いことは言ってない感も | |
| 火曜日になると論文読んだツイートが生えるのは火曜日に会社で論文読み＆紹介する会があるためで、月曜の晩になるとなんか面白論文ないかなーと探し始めて火曜日に読んだのをなんとなく消化できたらツイートしている感じです |