np-hard

2熱

3答えて

誰かがアルゴリズムを知っているかもしれません。あるいは、異なるサイズのバックパックに石（異なる重量）私はPrologでそれを行うべきです。私は石の重さとバックパックの容量を与えます。プログラムは、これらの石をどのようにバックパックに入れることができるのか、私に答えてくれます。

9熱

3答えて

NPハードとundecidable問題の関係

undecidable問題とNPハード問題の関係について少し混乱しています。 NP困難な問題が決定不能な問題のサブセットであるか、それとも単に同じで均等であるか、それとも同等ではないのか？私にとって、私は、決定不能な問題はNPの難しい問題のスーパーセットであると私の友人と主張してきました。 NPではなく、決めることのできない問題がいくつか存在します。しかし、私はこの議論が弱いと思っていて、ちょっ

25熱

2答えて

出発点に戻ることを考慮せずにトラベリングセールスマン問題（TSP）の問題名は何ですか？

私は、開始点に戻る方法とこれを解決するアルゴリズムを考慮して、TSPなしの問題名を知りたいと思います。私は、最短経路問題に見えたが、それは私が探していますものではありません、問題は2つの割り当てられたポイントからの最短経路を見つけます。しかし、私が探しているのは、私たちがnポイントを与え、開始点を1つだけ入力するという問題です。次に、すべてのポイントを正確に1回移動する最短経路を見つけます。（

7熱

1答えて

一般的にNP-hardであるが、平面グラフで多項式時間解を持つ問題のリスト？

グラフの問題として定式化できる多くの問題に遭遇しました。一般的にはNP困難ですが、グラフが平面であることが判明することがあります。したがって、私はこれらの問題とアルゴリズムを学ぶことに興味があります。私が知っている限りでは：平面グラフフォー着色立方平面グラフの平面グラフ最大独立集合にホープ誰かで最大カットこのリストを完成することができます。 NP完全問題のこのcompendiumで

0熱

1答えて

npハードに還元する

Wikiによると、ポリタイムでのnpコンプリートの問題をAに変換すると、Aはnpハードです。は http://en.wikipedia.org/wiki/NP-hardを参照してください。しかし、以下のPDFファイルを使用すると、多項式時間で問題AにNP困難な問題を変換するとき、AがNPであることを言う - http://compgeom.cs.uiuc.edu/~jeffe/teaching/

0熱

3答えて

Np硬度低下

問題がnp-hardであることを示したい場合は、既存のnp-hard問題を複数回使用するのは問題ありませんか？たとえば、ハミルトニアンサイクルをグラフでn回使用します（nは頂点の数です）。あるいは、グラフを1回使用された既存のnp-hard問題で簡単に解決できるものに変換する必要がありますか？