問題タブ [np]

たとえば、私はその言語を知っています

CFLのポンピング補題によって文脈自由ではありませんが、expではなくNPに分類されることをどのように証明しますか。時間、決定可能な言語、または認識可能なチューリング？

編集：いくつか掘り下げました、そして私がした一つの見落としは、NPの問題は非決定性チューリングマシンによって多項式時間で検証可能な問題であるということです。どうすればわかりますか：a：多項式時間でこの言語に存在するベリファイアがあり、b：NDTMがそれを認識できます

これは私の以前の質問(古いトップ コーダーのなぞなぞについて)のフォロー アップです。

数字の文字列が与えられた場合、その文字列が目的の数値に等しくなるために必要な加算の最小数を見つけます。各追加は、数字の文字列のどこかにプラス記号を挿入することと同じです。すべてのプラス記号が挿入されたら、通常どおり合計を評価します。

たとえば、「303」と目標の合計が 6 であるとします。最適な戦略は「3+03」です。

私は（それを証明していませんが）問題はNP完全だと思います。どう思いますか？よく知られている NP 完全問題をこの問題にどのように還元しますか?

なぜ 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 にある理由がわかりません。

このような数値の配列がいくつかあります（配列の各要素は0または1の値のみを取ることができます）

配列を合計したときに、結果の配列に 2 の倍数である個々の要素が含まれるようなサブセットを見つけたいと考えています。結果の配列は、2 の倍数である任意の値を持つことができます。

もう一つの例：

この例では、v1+v2+v5 と v3+v6+v7 が適切な回答です。

力ずくの解決策を念頭に置いていますが、より効率的な方法があるかどうかを確認したかったのです。これは部分和問題と同じですか?

すべての可能な独立集合の中から最大値を見つける力ずくの方法以外に、2部グラフで最大の独立頂点集合を見つけるためのアルゴリズムは存在しないと思います。

考えられるすべての頂点セットを見つけるための擬似コードについて疑問に思っています。

4つの青い頂点と4つの赤い頂点を持つ2部グラフが与えられたとしましょう。現在私は

最初のステップの後、すべての可能性をステップスルーするのではなく、一致しない次の色の頂点をすべて選択するため、この方法ではすべての可能な独立集合の組み合わせが得られるわけではないことを理解しています。

たとえば、一致するグラフがあるとします

このアルゴリズムを改善して、すべての可能性をより適切に検索する方法はありますか？|2部グラフの最大セット| =|赤| +|青| -|最大マッチング|。

問題は、特定の青に対して最初にすべての可能な赤を選択することによって、それらの赤が他のすべての可能な青に接続する場合、私のセットにはすべて1つの青と残りの赤しか含まれない可能性があるために発生します。

多項式時間で集合の分割を半分に解く可能性について読んだばかりです。しかし、それを行うためのアルゴリズムが見つかりませんでした。

2つの質問があります：

1. そのアルゴリズムはどこで入手できますか？
2. NP問題を多項式時間でどのように解決できるのでしょうか。

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

sum-subset 問題は次のように述べています。

整数の集合が与えられたとき、合計がゼロである空でないサブセットはありますか?

この問題は一般に NP 完全です。このわずかな変種の複雑さがわかっているかどうか、興味があります。

k整数のセットが与えられたとき、合計がゼロになるサイズのサブセットはありますか?

たとえば、 の場合k = 1、バイナリ検索を実行して で答えを見つけることができますO(log n)。の場合k = 2、次のように取得できますO(n log n)(たとえば、合計が指定された数値に等しい配列から要素のペアを検索するを参照)。の場合k = 3、実行できますO(n^2)(たとえば、合計が指定された数値に最も近い配列内の 3 つの要素を見つけるを参照してください)。

の関数としてこの問題に配置できる既知の境界はありkますか?

動機として、この質問について考えていました。2 つの部分の平均が等しくなるように、配列を 2 つの部分に分割するにはどうすればよいですか? 実際にNP完全かどうかを判断しようとしています。その答えは、上記の公式があるかどうかにあります。

一般的な解がなければ、 の最適な境界を知ることに非常に興味がありk=4ます。

非決定的多項式ソリューションは、決定的多項式ソリューションよりも常に望ましくありませんか? 適当な理由付けをお願いします。

有界係数。

数 n が与えられたとき、k より小さい適切な因数があるかどうかを判断します。

これはco-Npの問題ですか？