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
Here you go: Let's say you want to have sex with Natalie Portman (NP). Up until now, it was generally assumed that meant you had to satisfy three conditions: be rich, handsome, and fascinating. Unfortunately, any one of those would leave out the vast majority of people on this list; satisfying all three (3-SAT) was considered virtually impossible.
But now, Romanov claims that it is sufficient merely to say the mathematical equivalent of "Please" (P). Naturally, people are skeptical.
本家より。 (スコア: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:本家より。 (スコア:5, おもしろおかしい)
あんま英語読めないんだけど、読めた中から一番おもしろかったのはこの「そもそも3SATって何だよ」という質問に対するコメント。
http://science.slashdot.org/comments.pl?sid=1959038&cid=34942110 [slashdot.org]
大雑把な訳(間違ってたらごめんね。一部超訳)：
「試した中では全部成功した」ではなく「すべての場合において、成功する」ことを示さないとP=NPの証明にはならない。けれど二次元で試して全部成功したのだから、きっと有用なアルゴリズムなんだろうね。だったらいいな。
というお話なのかな。
Re:本家より。 (スコア:1, 参考になる)
fascinating は高学歴という意味ではないですね。
あと、
ではなくて、
というようなことが書いてあります。
Re: (スコア:0)
> fascinating は高学歴という意味ではないですね。
うん、そのへんが超訳。handsome, and fascinatingがイケメンに吸収されてしまったので3つになるように三高の定義から借りてきたの。
>> 数学的に「お願い」(Plaease, P) にあたることを言えばいい
> というようなことが書いてあります。
ことらは御意。
Re: (スコア:0)
fascinatingは外見のことではないよ。イケメンには吸収できない。
すごく面白い人という意味。（お笑いの面白いではなくて）