「distributed.net、25マークの最短ゴロム定規を導き出す」記事へのコメント

NP完全？

[Anonymous Coward]

NP完全 [wikipedia.org]ではなく、NP困難 [wikipedia.org]では？
NP完全であるためには、解が真に最短であることの検証が多項式時間でできる必要があると思いますが

Re:NP完全？

[deraok (37011)]

どうもNP困難性も未証明 [wikipedia.org]のようですが・・・
というか、最短ゴロム定規を「求める」のは明らかにNPに属さない（⇒NP完全ではない）ですね。