問題タブ [np-complete]

サブグラフ同型問題をサブセット和問題としてキャストして、サブセット和問題を解くために利用可能な動的計画法を使用して SGI 問題を解くことは可能ですか?

コインの最小変更問題は NP 完全問題ですが、コインの特定のセットでは貪欲なアルゴリズム (最初に最大の額面を選択する) が機能します。コインの値を表す一連の整数が与えられた場合、貪欲なアルゴリズムで十分かどうかを判断する最速のアルゴリズムは何ですか? 明白な方法の 1 つは、動的計画法のソリューションを最大額面まで構築し、貪欲な方法よりも優れたソリューションが得られるかどうかを確認することです。しかし、それを検出するためのより高速な「数学的な方法」はありますか?

この問題を証明するために、この割り当てがあります。

有限のアルファベット £、2 つの文字列 x、y € £*、および正の整数 K.単一の記号の削除または隣接する記号の交換の一連の K 以下の操作によって、文字列 x から文字列 y を導出する方法はありますか?

np-complete です。セットカバー問題の決定バージョンから変換を行う必要があることはすでにわかっていますが、これを行う方法がわかりません。どんな助けでも大歓迎です。

そのnを見るのは非常に簡単です！N乗（たとえば、100 ^ N）のほとんど何よりもゆっくりと成長するため、問題がNP完全であると見なされ、問題が発生した場合は！解を近似するアルゴリズムでは、スヌーピーダンスを行います。

この状況について2つの質問があります。

1. nだろう！アルゴリズムは多項式時間の解と見なされますか？階乗は確かに権力に引き上げられた用語ではないようです。
2. 見つけたら！解決策とは、かなり高速なアルゴリズムを使用していることを意味します。2 ^ Nよりも速く成長する場合、これは、一部のNP完全問題がヒューリスティック/近似アルゴリズムを必要としないことを意味しますか（あいまいな場合を除く）？

もちろん、これら2つの質問は、最初の段落が正しいことに依存しています。間違えた場合はお知らせください。

このXKCDコミックで言及されている問題に対するこのECLiPSeソリューションを見ました。私はこれを純粋なPrologに変換しようとしました。

これが、思いつくことができる最良の/最も宣言的な解決策ではないと思います。誰かが改善のための提案がありますか？前もって感謝します！

グラフ問題として定式化できる多くの問題に遭遇しました。一般にNP困難ですが、グラフが平面であることが証明される場合があります。したがって、これらの問題とアルゴリズムを学ぶことに興味があります。

私が知る限り：

1. 平面グラフの最大カット
2. 平面グラフの 4 色
3. 立方平面グラフの最大独立集合

誰かがこのリストを完成させてくれることを願っています。

私は削減について多くのことを研究しましたが、それには悪い問題があります：私はこれをCLRSから取っています：

「...問題Aの解決を問題Bの解決に「減らす」ことにより、Bの「容易さ」を使用してAの「容易さ」を証明します。」

そして、私はこれを「クリストスH.パパディミトリオウによる計算の複雑さ」から取っています。

「...問題Aは、BがAに減少した場合、少なくとも問題Bと同じくらい困難です。」

私はこれらの2つの概念と混同しました：簡単さを使用すると、問題Xは問題Yに還元され、Yの多項式時間アルゴリズムがあり、還元プロセスが多項式時間で行われる場合、問題Xは多項式時間で解くことができ、XはYより簡単か、少なくともYより難しくはありません。

しかし、硬さを使用すると、問題Xは問題Yに還元され、YはXよりも簡単であるか、少なくともXよりも難しくはありません。

私は本当に混乱しました、助けてください。特別な感謝。

NP完全であることが証明されていることは知っていますが、それで問題ありません。私は現在、通常のバイナリ平方/乗算アルゴリズムを使用する乗算の​​数に初期上限を設定する分岐限定法で解決しており、正しい答えが得られますが、実行には満足していません時間 (200 前後の数値の場合、数秒かかる場合があります)。これは NP 完全な問題であるため、目を見張るものは何も期待していません。しかし、多くの場合、実際の時間をある程度制御するためのトリックがあります。

実際にこれを行うためのより速い方法はありますか? もしそうなら、それらは何ですか?

NP完全の定義は

次の場合、問題は NP 完全です。

1. それはクラス NP に属します
2. NP の他のすべての問題は多項式に変換されます。

では、NP の他のすべての問題が NP 完全問題に変換される場合、それはすべての NP 問題も NP 完全であることを意味するのではないでしょうか? 2つが同じである場合、2つを分類するポイントは何ですか?

つまり、NP 問題がある場合、(2) を通じて、この問題は NP 完全問題に変換できます。したがって、NP 問題は NP 完全であり、NP = NP 完全です。どちらのクラスも同等です。

これを自分で明確にしようとしているだけです。

決定問題 A があり、それが NP 完全であることを示したい場合。別の NP 完全問題が多項式で A に還元されることを証明するだけで十分ですか、それとも別の NP 完全問題が多項式で A に変換されることを示す必要がありますか?

つまり、それを示すことができますか

または、示されているように、solve_A の使用は 1 回だけに制限されていますか?

一部の情報源は前者を言い、他の情報源は後者を言っていることがわかり、少し混乱しています.