問題タブ [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 の例はありますか?
ウィキペディアで NP と P を読んだところですが、2 つの質問があります。
- NP の例を多項式時間で解くことはできますか?
- 多項式時間で答えが得られる NP の例はありますか?</li>
big-o - NP完全な問題はNP困難でもありますか?
NP 完全問題は、NP および NP 困難な問題であると言えますが、NP 完全であるという事実だけで、問題が NP 困難であると排他的に主張することはできます。
例: NP 完全問題aをproblem に還元しますb。したがって、問題bは NP 完全であることが証明されました。実際、それも NP 困難であると言えますか?
algorithm - NP完全性の証明
グラフの任意の 2 つの頂点間の m 個の最短経路が与えられます。和集合がすべてのエッジをカバーするように k 個の最短パスを選択できるかどうかを判断します。
削減はセットカバーからでなければならないと確信していますが、それをこの問題に削減する方法がわかりません。それを手伝ってください
algorithm - ハミルトニアン経路が NP 完全であるのに、なぜ TSP は NP 困難なのですか?
これらの 2 つの問題、つまりTSPとハミルトニアン パスの問題がどちらも NP 完全ではないのはなぜですか?
それらは同一に見えます。
np-complete - 均一性制限のないハイパーグラフの頂点カラーリングは NP 困難ですか?
均一性制限のないハイパーグラフの頂点カラーリングは NP 困難ですか? k-unoform ハイパーグラフの頂点カラーリングが NP 困難であることを示す論文を見てきました。ただし、一般的な場合 (k-uniform だけでなく) ハイパーグラフでの頂点の色付けが NP 困難であるかどうかを明示的に示すソースを見つけることができませんでした。
optimization - 線形制約と二次制約を使用した二次計画法 (QP) の難しさ
ウィキペディア: 二次計画法では、線形制約のある正定値二次計画法 (QP) を多項式時間で解くことができると述べています。
一方、混合整数線形計画法 (MILP) は、二次制約付き二次計画法 (QCQP) に変換できます。MILP は NP 困難であることを知っているので、QCQD は一般的に NP 困難でなければなりません ( Wikipedia:Quadratically Constrained quadratic programから)。
つまり、制約に二次項がある場合、問題は NP 困難であり、それが目的関数にあり、正定である場合、多項式時間で解決できるということですか?