アカウント名:
パスワード:
そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。
(これが最短であることの検算も簡単ではないので明らかにNPに属さない)
「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。
なお、次数 25 のときのコメントで deraok さん [srad.jp]が
というか、最短ゴロム定規を「求める」のは明らかにNPに属さない（⇒NP完全ではない）ですね。
と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問題として、最短ゴロム定規を「求める」問題は判定問題でないので、明らかに NP に属さない、ということ。
実際には、習慣上、問題によっては判定問題でなくても「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:OGR-25確定時の関連ストーリーも参照 (スコア:2)
「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。
なお、次数 25 のときのコメントで deraok さん [srad.jp]が
と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問題として、最短ゴロム定規を「求める」問題は判定問題でないので、明らかに NP に属さない、ということ。
実際には、習慣上、問題によっては判定問題でなくても「NP に属する」とか「NP 完全である」という言葉を使う場合があるけれど、習慣として確立している場合以外に使うと意味が通じない。最短ゴロム定規を求める問題についてはそういう習慣が確立していないので、どういう判定問題を考えるのかを定義することなしにいきなり「NP に属する」と言ったら、意味が通じない。
Re: (スコア:0)
なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。
Re:OGR-25確定時の関連ストーリーも参照 (スコア:2)
どの問題のことを言っているのか不明。僕は #2553317 で NP に属する判定問題を 1 個も書いていない。
それは巡回セールスマン問題ではない。あえて呼ぶなら「巡回セールスマン検算問題」とでも呼ぶべき問題。同様に、
それは最短ゴロム定規問題ではなく「最短ゴロム定規検算問題」とでも呼ぶべき問題。
しかも、あなたの書いた問題はどちらも、 NP に属さないことは証明されていない。詳細は省くけど、これらの問題は coNP というクラスに属するので、仮にいずれかが NP に属さないことが証明されれば P≠NP が証明される。なので、仮に #2553224 が最短ゴロム定規検算問題のことを言っていたとしても、「これが最短であることの検算も簡単ではないので明らかに NP に属さない」と書いてあるのは依然として誤り。
Re: (スコア:0)
>なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
不自然でもなんでも、クラスNPに属するように書き換えない限りは、
「クラスNPに関する知識」という強力な道具を使って議論が出来ないので、しょうがないんです。
クラスNPに突っ込めないような、より特殊で複雑な問題をそのまま議論するのであれば、
クラスNPに関してよく知られた知識を使わずに頑張る必要があります。
どこから手を付ければ良いやらという話になりますので、ここでの雑談の域を超えるでしょ