NP問題 セールスマン問題

はじめまして。よろしくお願いします。
さて、N点を持つセールスマン問題が、
A=log N（底２）の時、NのA乗で処理できれば、問題が解決したといえるのでしょうか？又、このような解法は発見されているのでしょうか？

No.1 回答者： Tacosan 回答日時： 2009/11/06 02:37

「セールスマン問題」というのは「巡回セールスマン問題」のことかなぁ?

「解決した」とする問題はなんですか? もし TSP ∈ P なら, 全然解決できてないです.

この回答へのお礼

有難う御座いました。
まさに巡回セールスマン問題のことです。
さて、しつこいようですが、巡回セールスマン問題において、厳密解を
求めるには、一般的には（N-1)！/２ざくっといってN!だと理解しているのですが、現在これは、どの程度現実的な一般解（速度的に）が求められているのでしょうか？
参考になるサイトとかあれば、教えて頂きたいと思います。
よろしくお願いします。
又、TSP∈Pとは、解法に指数部分があってはならないという事でしょうか？基本的な事（まして難しい事）は分かっていません。
このような、薄学ものですが、どうか救いの手を延べてください。
よろしくお願いします。

お礼日時：2009/11/06 06:46