np-complete

1熱

2答えて

任意の（整数）金額のそれぞれのn個のチェックが、同じ金額の2つの部分にチェックを分割できるかどうかを判断すると、私はこの問題を解決する方法を忘れています。これを多項式時間で解くアルゴリズムはありますか？これはNP完全ですか？

1熱

2答えて

iが解決しようとしている問題に最もカラフルなパスを検索すると、このです：グラフG =（V、E）が与えられる毎エッジは、10色のうちの一つで着色し、そしてするよう2つの頂点：s、t。 sからtまでの（最短）パスを生成するアルゴリズムを見つける必要があります。これは、最小限の色を使用します。私の考えは、グラフを複製することだった10回：最初の重複は、第二のように... 2色の端のみを含めるとなり

5熱

1答えて

プロセッサ上でジョブをスケジューリングするアルゴリズム

iehrlichのコメント（thanks btw）によると、「スケジューリング」という用語は誤解を招く可能性があり、より適切な説明かもしれません。行列N * Nの場合、最大の対角の和です。私はNの仕事とN個のプロセッサのセットを持っています。すべてのプロセッサが互いに異なる場合があります。それぞれの（ジョブ、プロセッサー）ペアについて、そのプロセッサー上で実行されているそのジョブのパフォーマンス

0熱

1答えて

PARTITIONからSUBSET SUMへのKARPの削減

PARTITION：正の整数の集合A = {a_1、...、a_n}は、補数の和に等しい総和を持つAの部分集合が存在するか？ SUBSET SUM：正の整数A = {a_1、...、a_n}と別の正の整数Bの集合を考えると、その和がBに等しいようなAの部分集合が存在しますか？ PARTITIONがNP完全であれば、SUBSET SUMもPARTをSSUMに減らすことでNP完全であることを証明しよう

2熱

1答えて

C-SATとSATの違いは？

これらの2つのNP完全問題の違いは何ですか？ブール式を満たすことができるか（すなわち出力1）、一方は回路の文脈にあり、もう一方は単なる式であるかどうかを問われているように思える。しかし、ブール式回路からブール式を書くことはできませんでしたか？

0熱

1答えて

0,1ナップザックからサブセットの合計への還元

私はサブセットの合計を0,1回のナップザックに減らす方法を知っています。しかし、サブセット合計にナップザックを減らすことは可能ですか？どうやって？

1熱

1答えて

頂点カバーの近似アルゴリズム

PがNPと等しくない場合、kが固定定数である最適な頂点カバーのkに含まれる近似アルゴリズムがないことが分かりますか？

1熱

1答えて

NP-complete対NP-hard（なぜそれらは等しくないのですか）

なぜNP-hardはNP-completeと等しくないのですか？使用されている定義の私の非公式の理解： NP - 多項式時間で検証することができるすべての問題 NP完全 - NPとNP-ハードあるすべての問題NP-hard - NPの最も難しい問題と同じくらい難しいです。 Decision Problem - 入力に関して質問をしてブール値を出力する問題混乱： NP対Pの未知の解決策の問題は

0熱

1答えて

一定時間の擬ポリモニアル

偽多項式は、入力の大きさに対して多項式であるが、入力のサイズに対して指数関数的であることを意味します。したがって、ナップザックでは、O（nW）は擬多項式とみなされます。 nが大きくなると、nのビット長をもっと考慮する必要があるため、nとnyと呼ぶ人もいます。その多項式とみなせる変数を持つものは、実際には擬多項式であるということは本当ですか？

2熱

1答えて

すべての文字列パーミュテーションNP Completeを生成していますか？

与えられた文字列のすべての文字列置換を計算することは、すべての可能性を試すことによってO（n！）で解決できます。さて、旅行の巡回セールスマン問題を見て、我々は都市のすべての順列を試みることによってそれを解決することができます。我々はA、BおよびCのたちはABCのACBを取得BC文字列のすべての順列を計算することによって、我々は都市Aで開始すると言うことができます都市、そして我々はただの和（のた