This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we wait for on the experts on this paper isn't "is it correct" (it probably is) but "how effective is it".
The main experimental results presented more than 1000 testing runs for formulas with pa- rameters: n > 25, 100 ≤ m ≤ 1000, including n = 100, m = 1000 in a pair. The typical computing time values (in minutes) were: τ < 1 for n ≤ 50; τ = 1 ÷ 3 for n = 64; τ = 5 ÷ 8 for n = 80
本家より。 (スコア:3, 参考になる)
あんま英語読めないんだけど、読めた中から一番興味深かったのはこれ。
http://science.slashdot.org/comments.pl?sid=1959038&cid=34942460 [slashdot.org]
This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we wait for on the experts on this paper isn't "is it correct" (it probably is) but "how effective is it".
大雑把な訳(間違ってたらごめんね)：これはP=NPを示した論文じゃない。この論文で、多項式時間で、関連したデータ構造(?)の問題を解けて、それがいくつかの3SAT問題の解法として使用できることが示された。このアルゴリズムは次の3つの出力を返すことができる。「その式は充足しえない」、「その式は充足しうる」、「分類に失敗した」(問題を解けなかった)。これでは、問題が解かれたとはいえない。専門家に期待すべきなのは「このアルゴリズムは正しいか？」ではなくむしろ「どれくらいこのアルゴリズムが効果的か？」を評価してくれることだ。(アルゴリズムは多分正しい)
一応、論文中には、
The main experimental results presented more than 1000 testing runs for formulas with pa-
rameters: n > 25, 100 ≤ m ≤ 1000, including n = 100, m = 1000 in a pair. The typical
computing time values (in minutes) were: τ < 1 for n ≤ 50; τ = 1 ÷ 3 for n = 64; τ = 5 ÷ 8
for n = 80
1を聞いて0を知れ!
Re:本家より。 (スコア:2, 興味深い)
3SATのソルバーはnが小さい(と言っても10万くらい)うちは優秀なものがいくらでもあるので、少なくともそれらよりは性能がいいことを示さないと意味がありません。
一般にオーダーに支配されるのはnが無限に大きくなったときで、nが小さいうちなら一見効率がよく見えるものはありふれています。たとえばほとんどのコンピュータにはたかだかn＜2^32やn＜2^64のときにはO(1)で乗算を行う演算器が付いていると思いますが、たとえばπを5兆桁求めようと思ったら [srad.jp]素朴に計算しているときっちりO(n^2)に支配されるので、ちゃんとFFTなど(真に)高速なアルゴリズムを採用する必要があります。
Re: (スコア:0)
> n＜2^32やn＜2^64
big-O表記のnは入力のサイズを表しますから、入力が数字1つならその桁数、つまりn＜32とかn＜64で表すのが適切です。テープに2^64種類の文字が書けるならどちらもn=1ということになるので同じになるのは当たり前ですね。テープに書ける文字の種類を増やすことで、定数倍ならいくらでもチューリングマシンを速くできるという定理があって、線形加速定理 [dendai.ac.jp]と呼ばれています。プログラマにとって直感的に分かりやすい表現をするなら「64ビットマシンは32ビットマシンより速い」「ソフトウェアでロジックを実現するよりハードウェアのほうが速い」ということです。