問題タブ [np-hard]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - ナンバーリンク/フロー ゲーム: NP 完全問題を見つけるには?
有名なゲーム Flow の問題を解決する方法を見つけようとしていました。http://moh97.us/flow/
グーグルで調べたところ、これはNP完全な問題であることがわかりました。良い解決策は、ヒューリスティックとカットを利用することです。NP 完全問題を簡単に見つけるにはどうすればよいですか? ブロックすると、明らかな解決策が見えないことがあります。これが NP 完全で発生した場合は、すぐに認識して次の問題に進む方がよいでしょう。
algorithm - NP-完全 VS NP-ハード
NP-Complete と NP-Hard の違いを理解しようとしています。
以下は私の理解です
NP 困難な問題は、多項式時間では解けないが、多項式時間で検証できる問題です。
NP 完全問題は、NP 内にあり、NP 困難でもある問題です。
上記の定義は正しいですか？もしそうなら、NP ではなく NP-Hard の問題についてはどうですか。それらは NP 完全問題よりも難しくないでしょうか? 指数時間でしか解決および検証できないと言うのですか?
complexity-theory - NP-complete の複雑度測定
たとえば、集合カバー決定問題は NP 完全問題として知られています。この問題の入力は、ユニバース U、U のサブセットのファミリ S、および整数 k () です。
私が混乱していることの 1 つは、k=1 とすると、S の各要素をチェックするだけで、明らかに時間 |S| で問題を解決できるということです。より一般的には、k が定数の場合、問題は次のようになります。 |S| の多項式時間で解かれます。このように、|S|/2、|S|/3... のように、k も |S| とともに増加する場合にのみ、時間計算量は指数関数的に高くなります。
だからここに私の質問があります：
私の現在の理解では、NP 完全問題の時間計算量の測定は、最悪のケースで測定されます。理解が正しいかどうか誰か教えてください。
私は誰かが別の問題が NP 困難であることを証明するのを見ました
<U,S,|U|/3>。なぜ彼は??<U,S,|U|/3>ではなく、だけを証明したのだろうと思っています。<U,S,ARBITRARY k>そのような証拠は信頼できますか？
どうもありがとう！
complexity-theory - 一部の NP 完全問題が NP 困難である可能性があるのはなぜですか?
P、NP、NP-Complete、および NP-Hard を直感的な方法でラップして、それらの定義を覚える必要がないようにしています。
次の図 (左側のシナリオ、P != NP) では、NP-Complete と NP-Hard の間に重複領域があります。一部の問題が NP-Complete と NP-Hard の両方であるということですか? この特定の回答によると、矛盾していると思います：NP、NP-Complete、NP-Hardの違いは何ですか？.
上記のリンクの表は、NP 完全問題は多項式時間で検証可能であり、NP 困難問題はそうではないことを示しています。では、どのように重複があり得るのでしょうか?
complexity-theory - 多項式時間近似スキームの理解
近似アルゴリズムは多項式時間近似アルゴリズム (PTAS) と同じですか? たとえば、頂点カバーの A(I) <= 2 * OPT(I) を示すことができます。Vertex Cover には 2多項式時間近似アルゴリズムまたは PTAS があるということですか?
ありがとう！
注: 斜体のテキストは、質問を投稿した後に行った編集です。
complexity-theory - シュタイナー極小木と NP 完全性
次のシュタイナー木の違いは何ですか: (非) メトリック シュタイナー最小木、ユークリッド シュタイナー最小木、グラフ シュタイナー最小木など? これらのうちどれが NP 完全で、どれが NP 困難ですか? 私が見つけたオンライン リソースの中には、シュタイナー木が NP 困難であることを示唆するものもあれば、NP 完全であることを示唆するものもありますが、それらは問題のさまざまなバージョン/バリアントを参照していると思います。
更新：気にしないでください、私はそれを理解しました。SMT の決定問題は、シュタイナー木と整数 k が与えられた場合、木のコストが k 以下かどうかを多項式時間で簡単に検証できるため、NP 完全です。しかし、SMT の最適化問題には多項式時間検証器がありません (ツリーのコストを見つけることはできますが、それが最適解であることを検証することはできません)。そのため、NP 困難です。
algorithm - TSP メトリックの近似の証明
次の質問に行き詰まりました。
次のヒューリスティックを考えてみましょう: 頂点を 1 つだけ含むツアーから開始します。各ステップで、ツアーの頂点までの距離が短いツアーの外側の頂点を見つけます。v を外側の頂点、u を内側の頂点とします。ツアーの u の直後に v を追加します。エッジが三角形の距離プロパティに従うとします。このヒューリスティックが TSP メトリック問題の 2 近似であることをどのように示すことができますか?
誰もそれを開始する方法を知っていますか?
前もって感謝します