問題タブ [np-complete]

tardos のアルゴリズム設計書から NP 完全性について読んでいます。サブセット和が NP 完全であることを証明するセクションでは、次のように書かれてい
ます。サブセット和用に開発されたアルゴリズムの実行時間は O(nW) です。それぞれが 100 ビット長の 100 個の数値のインスタンスが与えられた場合、入力は 100 * 100 = 10000 桁にすぎませんが、W はおよそ 2^100 です。
この主張が理解できません。なぜ W 2^100 なのですか? この問題に対する base の影響は何ですか? つまり、それを別の base x に変更すると、W は x^100 になりますか? 単項ベースに変更するとどうなるでしょうか?
ありがとう。

なぜ 2-CNF SAT が P にあり、3-CNF SAT が NPC にあるのか、本当に混乱しています。CLRS を読んで、3-CNF SAT が NPC にあることを証明する方法を理解しています。SAT から 2-CNF-SAT への同じ還元可能性を使用して、2-CNF-SAT が NPC にあることを証明することはできませんか? 2-CNF SAT が P にある理由がわかりません。

SATがNP完全であるという証明は構成的証明であるため、プログラムとして実装できるはずです。誰かがこれをしましたか？

プログラム（trueまたはfalseを返す）を入力として受け取り、SAT式を出力するプログラム（コンパイラー）を探しています。

したがって、たとえば、コンパイラは次のプログラム（pythonic構文で表示されますが、どの言語でも問題ありません）を入力として受け取り、SAT式を出力できます。SAT式をSATソルバーにフィードすると、パラメーター「証明書」の解が得られます。この場合、解は[False、True、True、True、False]になり、{-3、-2、5}が解であることを示します。

明らかに、出力SAT式には他の補助変数があるため、コンパイラーはどの変数が証明書に対応するかを示す必要があります。

そのようなコンパイラはすでに存在しますか？それらのいずれかがオープンソースですか？

有向非巡回グラフがあり、リソース制約のある最短経路を見つける必要があります。私の制約は、選択されたパスは、消費されるセット リソースの最小数を持たなければならないということです。

現在、Yen の K 最短パス アルゴリズムを使用して K 最短パスを計算し、制約を満たすパスのみを受け入れています。ここで問題となるのは、K を推測することです。誤って選択された場合、実行可能なパスが見つからない可能性があります。

このトピックに関するかなり多くの文献を見つけました。これは良い概要を提供すると思います。しかし、私はそれを理解し、実装できる簡潔なアルゴリズムを見つけるのに苦労しています (私は Python を使用していますが、明確なアルゴリズムのアイデアは素晴らしいでしょう)。

この問題は NP-Complete であることを理解しています。そのため、適切な近似アルゴリズムと正確なアプローチに興味があります。

誰にも良い推奨事項はありますか？

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

私はランダムな無向ソーシャルグラフを持っています。

できればハミルトン路を見つけたいです。または、不可能な場合（または多項式時間で可能かどうかを知ることができない場合）、一連のパス。この「一連のパス」（N個のノードすべてが1回だけ使用される）では、パスの数を最小限に抑え、パスの平均の長さを最大限に増やしたいと思います。（したがって、単一ノードのNパスの自明な解決策はありません）。

すでにノードとエッジの隣接行列を生成しました。

助言がありますか？正しい方向へのポインタ？問題のNP完全（？）の性質のため、これにはヒューリスティックが必要になることを認識しており、「十分に良い」答えで大丈夫です。また、Javaでこれを実行したいと思います。

ありがとう！

ウィキによると、ポリ時間の np complte 問題を A に変換すると、 A は np ハードです。http://en.wikipedia.org/wiki/NP-hardを参照

しかし、以下の pdf は、多項式時間で np ハード問題を問題 A に変換すると、A は np ハード http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard であると述べています。 pdf

どっちを信じればいい?

私はコンパイラ/プルーフチェッカーに取り組んでいますが、次のような構文ツリーがあるかどうか疑問に思っていました。たとえば、次のようになります。

sのアルファ等価性（等価モジュロ名前変更）をチェックする方法があった場合Expr。ただし、これExprはラムダ計算とは異なり、ラムダ内の変数のセットは可換です。つまり、パラメーターの順序はチェックに考慮されません。

（ただし、簡単にするために、とLambda ["x","y"] ...は異なりLambda ["x"] (Lambda ["y"] ...)ます。その場合、順序は重要です）。

言い換えると、2つが与えられたExprs場合、1つが一方から他方への名前変更を効率的に見つけるにはどうすればよいでしょうか。この種の組み合わせ問題は、NP完全のにおいがします。

次の問題のアルゴリズムを構築するのに助けが必要です。

他のポイントCを「見る」ことができるポイントGのセットがあります。GからCのすべてをカバーする最小セットを見つけるアルゴリズムが必要です( Gは必ずしもCの一部ではありません)。

これは動的計画法で解決すべきだと感じています。しかし、私は私を助けることができる解決策/アイデアに対してオープンです.

ありがとう！

編集1：

問題を完全に理解していない可能性があります。

ポイントは、地形の高さを持つ 3D サーフェス上にあります。地形はポイント間で特定の高さまで上昇する可能性があり、ポイントが他のポイントを見ることができないようになります。直接の視線がある限り、距離に関係なく、ポイントは互いに見ることができます。

• 点a ( Gから) が点b ( Cから) を見ることができ、点bが( Cから) dを見ることができる場合、 aはdを見ることができます。これが違いを生むかどうかはわかりません。

• a ( Gから)だけがb ( Cから) を見ることができる場合、すべてのCをカバーするためにaを選択する必要があります。

新しい情報に照らして、他に違いがあるかどうかはまだ考えています.

次の問題を考えてみましょう。

1からNまでの番号が付けられたN枚のコインがあります。

あなたはそれらを見ることができませんが、次の形式のそれらについてのMの事実が与えられます：

positionsコインのサブセットを識別し、num_headsそのサブセット内のヘッドであるコインの数です。

これらのMの事実を考えると、おそらく存在する可能性のあるヘッドの最大数を計算する必要があります。

この問題はNP完全ですか？はいの場合、削減は何ですか？いいえの場合、多項式時間解とは何ですか？

例えば：

事実に一致するヘッドが最も多い構成は次のとおりです。

したがって、答えは3つの頭です。