ノート:巡回セールスマン問題

NPO困難 -> NP困難 ???

最適化問題の記事にもPO、NPOという赤リンクがあります。 NPOという（数学あるいは数値解析）用語があるのでしょうか？。219.108.13.78 11:39 2003年7月31日 (UTC)

昔、グラフ理論専攻だったんだけど、聞いたこと無い。でも、お情けで修了させてもらった220.145.148.95は、有識者の登場を待ちます。

ノート:最適化問題にも書きましたが、そういう計算量のクラスが存在します。ただ、この記事の場合、NP困難, NPO困難のいずれも正しいです。Ojigiri 11:53 2003年7月31日 (UTC)

失礼しました。

すみません、最適化問題のノートは見てませでした。219.108.13.78 12:12 2003年7月31日 (UTC)

NP困難と実時間解決について

よく誤解されているが、NP困難な問題は、任意の大きさの任意の問題例に対しての多項式時間アルゴリズムが存在しないと考えられているのであって、

とありますが，問題の大きさに上限を持たせた時点でNP困難の議論をすることに意味が無いし、特別な問題例の場合に多項式時間解法があるとすれば、それは元の問題に対して何らかの制約条件が付された、あるいは、外されたからではないでしょうか？ここでは「NP困難な問題とはいっても、ある程度問題の大きさが小さければパーソナルコンピュータでも現実的な時間で厳密解を導くことが可能です。」と修正されることを希望します。--この署名のないコメントは 2007年7月30日 (月) 00:02 (UTC) に 202.223.156.24 によって投稿されました。

サイズが小さい場合でも最良の解を見つける最良のアルゴリズムがあるかという問題です。--116.64.208.207 2015年11月16日 (月) 15:45 (UTC)[返信]

欧州とアメリカの傾向への言及

文中「より複雑な定義の問題をあつかう解法としては、欧州では〜、アメリカ合衆国では〜」という記述がありますが、そもそも意味が不明瞭な上に、そうした傾向についての調査があるとも信じがたいです。

履歴を辿ってみるとこれは2004年11月12日に書かれた記述なのですが、このときは文脈として「実際の応用事例では、制約付きのもう少し複雑な形として配送計画に適用される。この場合の解法としては」という前振があり、独自調査の趣はありますが、それでもまだ意味が取れる記述です。これが編集を重ねるうちに次第に不明瞭化しています。

もはや元の文意を辿ることも難しそうですし、削除してはいかがでしょうか。--福地健太郎（会話） 2016年5月7日 (土) 16:36 (UTC)[返信]