3SAT問題を多項式時間で解くアルゴリズムが発表される。P=NP証明に？ 19
ストーリー by hylom
世紀のアルゴリズムか、それとも 部門より
世紀のアルゴリズムか、それとも 部門より
あるAnonymous Coward 曰く、
本家/.によると、Vladimir Romanov氏が、3SAT問題を解く多項式時間アルゴリズムなるものをリリースしたそうだ（該当のブログエントリ） 。
3SAT問題はNP完全なので、この主張が正しければ、P=NPであることになる。ソースコードはGitHubにて公開されている 。
NP完全問題と3SAT問題の関連については東京電機大学坂本直志准教授の講義資料などが参考になる。
本家より。 (スコア: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; τ = 20 ÷ 25 for n = 100.
(略)
The first or the second messages terminated each run of the program, the third message (引用者注: 「分類失敗」の出力)
didn’t occur at all.
とあるけど、「試した中では全部成功した」ではなく「すべての場合において、成功する」ことを示さないとP=NPの証明にはならない。けれどいっぱい試して全部成功したのだから、きっと有用なアルゴリズムなんだろうね。だったらいいな。
というお話なのかな。
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は外見のことではないよ。イケメンには吸収できない。
すごく面白い人という意味。（お笑いの面白いではなくて）
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ビットマシンより速い」「ソフトウェアでロジックを実現するよりハードウェアのほうが速い」ということです。
月刊P=NP?問題 (スコア:1, 参考になる)
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm [win.tue.nl]
毎月のようにP=NPであることが証明されたりP≠NPであることが証明されたり忙しいですね。
Re:月刊P=NP?問題 (スコア:1, 興味深い)
逆にどこが間違ってたか毎月種明かしして欲しいですね。
中にはなんだこんなの世に出すなよってへぼい証明もありそう。
10年も前に解決済だというのに！ (スコア:1)
P=NP問題なぞ、人類の神こと山口人生様が10年も前に解決しているというのに！
http://www.int2.info/news1.htm [int2.info]
#超高出力電波注意
元大学准教授だったというのが信じられん
TSP は NP 完全問題？ (スコア:0)
Re: (スコア:0)
Re:TSP は NP 完全問題？ (スコア:2, 参考になる)
NP完全問題が「あらゆるクラスNPの問題より難しく(すなわち、その問題を速く解くアルゴリズムを応用すれば全てのクラスNPの問題がさくさく解ける)」「YesかNoか?を求める問題」と定義できるから。
基本的に完全問題バージョンと困難問題バージョンがある問題の場合は、どっちかを速く解けるアルゴリズムが見つかれば逆もまたしかりなので、厳密な議論をしている場合を除くと意識してない事が多く、慌ててしゃべってるときなんかはちょいちょい言い間違えるorz
ちなみに、逆もまたしかりなのは、「最も安い経路」が求まるなら、「予算内の経路」があるかどうかは自明。 その逆は、コストの最大値を求めて二分探索でもすればよい(線形探索でもかまわない)。まず、全部の道の費用を単純に全部足して架空の「最大コスト」を求める。TSPだと同じ道を2回以上通る経路は解にはならないので、ここで求めた「最大コスト」より費用のかかる解は存在しない(極端な場合を除くと「最大コスト」になる経路も存在しないけど)。そこで、この「最大コストの半分のコストの道はあるかないか?」を判定する。あれば「さらにその半分」・・・とやっていく。酷い話だけど、ここまでやっても、判定に使うのが「TSP判定問題を多項式時間で解くアルゴリズム」なら、最安値を求める問題も「多項式時間で解ける」ことになる。
Re: (スコア:0)
NP-hard と呼ばれるのは、TSPで予算内に収まるかどうかだけでも既に NPC なので、最安値はいくらかとか、最安経路を求めるなど様々な実用的なバリエーションに予算内判定を帰着できるからでしょう。
で、二分探索を簡単に考えていますが、「解ける」をどう捉えるかが問題です。 非決定性の計算は受理計算が存在するかだけなので、単なる非決定性のチューリング機械では多項式時間で最安値を求めることも、与えられた値が最安値かどうかを判定することもできないと思います。 予算内判定を多項式時間で yes, no を判別できれば最安値判定問題が解けます(Δp 2-completeだったはず)。 あと、最安経路は複数存在しますので、予算内判定問題が簡単でも最安経路を求めるのはそれほど自明ではありません(関数のクラスとしてはΔp 2MVかな？)。
Re:TSP は NP 完全問題？ (スコア:1)
Re:TSP は NP 完全問題？ (スコア:1, おもしろおかしい)
計算量がうまく見積もれないのですが、「ケーサツ呼びますよ」「ケーサツ呼びましたから」「あー、もしもし、ケーサツですか」といったケーサツアルゴリズムは割と効果的に問題を解決するようです。
Re: (スコア:0)
>居直りセールスマン問題とか
もしかして、開き直りのつもり？
Re: (スコア:0)
元AC氏ではありませんが、「居直る」という言葉には「無作法や罪を咎められて態度を荒らげる」、今風に言うと「逆切れ」の意味があります。
ちょうど昨日、我が家に来た野菜訪問販売のおばちゃんが、近隣家庭の情報を我が母上から聞きだそうとし、断ったらなぜか怒り出した（「一軒一軒訪問しなきゃならんのか」とか。当たり前でしょうが）というエピソードがあったそうです。
そうした迷惑な「居直りセールスマン問題」を解決するスマートなアルゴリズムがあったら、実用度が高いのではないでしょうか。