問題が np-hard であることを示したい場合、既存の np-hard 問題を複数回使用しても問題ありませんか? たとえば、n が頂点の数であるグラフでハミルトニアン サイクルを n 回使用しますか? または、グラフを、1回使用された既存のnp困難な問題で簡単に解決できるものに変換する必要がありますか?
質問する
333 次
3 に答える
4
正反対を示す必要があります。
NP 困難な問題で問題を解決できることを証明しても、何も証明されません。[ Cook-Levin の定理により、SAT を使用して NP のすべての問題を解決できます]。
問題が多項式時間で解けるかどうかを示す必要があります-NP-Hard問題もそうです。それが削減が実際に行うことです。
例: TSPを使用して最短経路を解決できることを示すことができれば、最短経路は NP 困難になりますか? もちろん違います！TSP が少なくとも最短経路と同じくらい難しいことを示しているだけです。
于 2012-01-09T13:40:31.693 に答える
1
パリからロンドンを経由してニューヨークを経由することは、その道が最短の道であることを証明するものではありません。
于 2012-01-09T14:10:41.397 に答える
0
私は数学者ではありませんが、問題の問題が既存の既知の NP 困難な問題、またはその倍数と少なくとも同じくらい複雑であることを証明できれば、それは十分な証拠になるはずですか? ヒョウの皮を剥ぐのが 2 匹の猫の皮を剥ぐより複雑なら、1 匹の猫の皮を剥ぐよりも複雑だというのが常識です。
于 2012-01-09T13:36:48.660 に答える