アカウント名:
パスワード:
そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。
(これが最短であることの検算も簡単ではないので明らかにNPに属さない)
「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。
なお、次数 25 のときのコメントで deraok さん [science.srad.jp]が
というか、最短ゴロム定規を「求める」のは明らかにNPに属さない(⇒NP完全ではない)ですね。
と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問
なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。
なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
どの問題のことを言っているのか不明。僕は #2553317 で NP に属する判定問題を 1 個も書いていない。
巡回セールスマン問題なら「与えられた経路は最短かどうか」
それは巡回セールスマン問題ではない。あえて呼ぶなら「巡回セールスマン検算問題」とでも呼ぶべき問題。同様に、
最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」
それは最短ゴロム定規問題ではなく「最短ゴロム定規検算問題」とでも呼ぶべき問題。
しかも、あなたの書いた問題はどちらも、 NP に属さないことは証明されていない。詳細は省くけど、これらの問題は coNP というクラスに属するので、仮にいずれかが NP に属さないことが証明されれば P≠NP が証明される。なので、仮に #2553224 が最短ゴロム定規検算問題のことを言っていたとしても、「これが最短であることの検算も簡単ではないので明らかに NP に属さない」と書いてあるのは依然として誤り。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
アレゲは一日にしてならず -- アレゲ研究家
OGR-25確定時の関連ストーリーも参照 (スコア:1)
そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。
Re: (スコア:2)
「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。
なお、次数 25 のときのコメントで deraok さん [science.srad.jp]が
と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問
Re: (スコア:0)
なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
どの問題のことを言っているのか不明。僕は #2553317 で NP に属する判定問題を 1 個も書いていない。
それは巡回セールスマン問題ではない。あえて呼ぶなら「巡回セールスマン検算問題」とでも呼ぶべき問題。同様に、
それは最短ゴロム定規問題ではなく「最短ゴロム定規検算問題」とでも呼ぶべき問題。
しかも、あなたの書いた問題はどちらも、 NP に属さないことは証明されていない。詳細は省くけど、これらの問題は coNP というクラスに属するので、仮にいずれかが NP に属さないことが証明されれば P≠NP が証明される。なので、仮に #2553224 が最短ゴロム定規検算問題のことを言っていたとしても、「これが最短であることの検算も簡単ではないので明らかに NP に属さない」と書いてあるのは依然として誤り。