「次数27の最短ゴロム定規（OGR-27）が確定」記事へのコメント

OGR-25確定時の関連ストーリーも参照

[Anonymous Coward]

そっちにはNP完全問題って間違ったことが書かれてコメントで突っ込まれてるけど(これが最短であることの検算も簡単ではないので明らかにNPに属さない)。

Re:

[fcp (32783)]

(これが最短であることの検算も簡単ではないので明らかにNPに属さない)

「検算が簡単ではない」と言っても、今のところ検算を効率良く行う方法が知られていないというだけなので、それを理由に「明らかに NP に属さない」と言うことはできないよ。

なお、次数 25 のときのコメントで deraok さん [science.srad.jp]が

というか、最短ゴロム定規を「求める」のは明らかにNPに属さない（⇒NP完全ではない）ですね。

と書いているのは、 NP というのが「はい」か「いいえ」で答えられる問題 (「判定問題」と呼ばれる) のクラスだからだと思う。検算が簡単かどうか以前の問

Re:

[Anonymous Coward]

なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。
巡回セールスマン問題なら「与えられた経路は最短かどうか」最短ゴロム定規問題なら「与えられたY次ゴロム定規は最短かどうか」というのは自明すぎてわざわざ言うまでもないと思ってたのに2つも独立して突っ込まれてるし。

Re:OGR-25確定時の関連ストーリーも参照

[Anonymous Coward]

コメント先を間違えておられる気がしましたので、コメント返します。

>なんか問題をクラスNPに属するようにするためだけに不自然な書き換えしてるように見えるんだけど。

不自然でもなんでも、クラスNPに属するように書き換えない限りは、
「クラスNPに関する知識」という強力な道具を使って議論が出来ないので、しょうがないんです。

クラスNPに突っ込めないような、より特殊で複雑な問題をそのまま議論するのであれば、
クラスNPに関してよく知られた知識を使わずに頑張る必要があります。
どこから手を付ければ良いやらという話になりますので、ここでの雑談の域を超えるでしょう。

>巡回セールスマン問題なら「与えられた経路は最短かどうか」

そういうふうに、「自然に」書き換えても、NPに入らないのでしょうがないんです。

クラスNPに突っ込むためには、「多項式時間で判定可能な判定」である必要があります。
なぜ必要かというと、それがルールだからです。
と言うと乱暴なんですが、そのルールを前提にいろいろと考えに考え抜かれたのが、
今の広く知られるクラスNPに関する知識ですから、ルールを無視するとその知識も使えなくなります。

例えば、将棋の様々な定石は、将棋のルールの上で考えられたものなので、
チェスなどそれ以外のルールでは役に立たないのと同じです。

「それが最短か?」は、ほぼ巡回セールスマン問題そのものですので、
それを多項式時間で判定できるアルゴリズムを作れれば、P=NPを証明した事になります。

巡回セールスマン問題を「与えられた経路は最短かどうか」と書き換えても、もちろん構いません。
構いませんが、その問題は、クラスNPには属さないと考えられており(もしP=NPならば属するのでこういう微妙な表現になります)、
「NP問題が持つと知られている性質」を持ち出してくるのはお門違いとなり、そのような書き換えは功を奏さない結果になります。