問題タブ [np-complete]

私は部分集合問題の非常に明確な例である問題を抱えています:

「範囲 [-65000,65000] の整数のリストが与えられた場合、合計されたリストのいずれかのサブセットがゼロに等しい場合、関数は true を返します。それ以外の場合は false を返します。」

私が聞きたかったのは、解決策というよりも説明です。

これは、問題の複雑さについて考える前に思いついたインスタンス固有の解決策でした。

• 配列 A[] を並べ替え、並べ替え中に各要素をカウンター 'extSum' (O(NLogN)) に合計します。
• ポインター low = A[0] および high = A[n-1] に定義します。
• 決定的なコードは次のとおりです。
• /li>

まず、この解決策は正しいですか？いくつかテストしましたが、よくわかりません... 簡単すぎて...
このコードの時間計算量は O(n^2) ではないでしょうか?

私はすでにさまざまな DP ソリューションを読みましたが、理解したいのは、私が直面している問題の特定のインスタンスについて、この素朴で直感的なソリューションよりもどれだけ優れているかということです。私のアプローチは大幅に改善できることはわかっていますが、時間の複雑さに関しては大きな違いはありません....

説明ありがとうございます

編集:明らかな最適化の 1 つは、並べ替え中に 0 が見つかった場合、関数はすぐに true を返すことです....しかし、配列に 0 がある特定のケースのみです。

次の NP 完全問題があります。

与えられた:

• N × N フィールド内の位置のセット、
• m 個のノードのセット、および
• ノードの接続性グラフ (つまり、エッジが互いに接触しているノードのすべてのペアを表す無向グラフ)、および
• 接触範囲 R (N × N フィールドと同じ長さ単位)、

接続グラフを考慮してフィールド内のノードの配置を見つける (つまり、接触しているペアが R よりも近く、接触していないペアが R よりも遠いようにノードを配置する)、またはそのような配置が存在しないことを示します。

この問題を還元できる有名な NP 完全問題はありますか?

(問題の最適化バージョン、つまり最適な配置を見つけることも考えられます)

Bounded Degree Spanning Tree が次数または 2 の NP 完全と見なされる理由は理解していますが (これはハミルトニアン パス問題のインスタンスです)、なぜこれが次数 > 2 に適用されるのかわかりません。次数が 2 を超える NP 完全問題。

3SAT≤p3COLOR（つまり、3SATは3COLORに還元可能な多項式時間）であることがわかっています。なぜ3COLOR≤p3SATなのか、誰かが短い議論をすることができますか？そして、3COLOR≤p3SATであることを示す実際のクックリダクションを与えてください。

こんにちはみんな質問があります。誰かがそれを証明する方法を知っているかどうか疑問に思います。

ここに質問があります：サブセット和問題はNP完全であることが示されています。入力は、正の数w1、...、wn、Wのシーケンスです。ここで、Wはターゲットの重みです。問題は、いくつかの重みの合計が目標の重みに等しくなるように、重みのセットF⊆{1、...、n}があるかどうかを判断することです（つまり、w1 + ... + wi = W）
。制限付きサブセット和問題はサブセット和のように定義されますが、ターゲットの重みがすべての重みの合計の半分未満であるという追加の要件があります。（これが失敗した場合、入力はすぐに拒否される必要があります。）制限付きサブセット和がNP完全であることを示します。
ありがとうございました。

問題: それぞれが特定の時間枠 (7 つの時間枠がある) でのみ利用可能な一連の必須およびオプションのコースが与えられた場合、可能なすべての時間割を生成します。

例：

必修科目の場合：

• MAT101 - 1、2、5
• HIS102 - 2、4、6
• ENG105 - 3、6、7

オプションのコース:

• LIT103 - 3、4、6
• CHE101 - 7、1、2
• BIO101 - 5、4、7
• MAT201 - 6、5、1
• ANT201 - 1

（すべてのオプションコースを時間割に含める必要はありません）

可能な解決策の1つは次のとおりです。

1. MAT101【必須】
2. HIS102【必須】
3. LIT103
4. BIO101
5. MAT201
6. ENG105 [必須]
7. CHE101

PHPでそれを書く最も効率的な方法は何ですか?

私は現在、ブルート フォース ソリューションを開発しようとしていますが、それは非常に退屈な作業であり、より効率的な方法を探しています。これは NP 完全問題であることがわかり、そのような問題を解決するのに役立つ PHP クラスを探しましたが、残念ながら現時点ではそのようなクラスはありません。

NP完全であることがわかっている問題Aを多項式時間で別の問題Bに還元できる場合、Bは（A）NP完全（B）NP困難です。

問題BがNPにあるかどうかにかかわらず、問題Bについては何も示されていません。Hopcraft and Ullmanの本には、NP完全問題P1を多項式時間で問題P2に還元できる場合、P2はNP完全であるという定理があるため、私は混乱しています。ただし、問題がNP完全である必要があり、それがNPクラスに属している必要があります。男はこの概念を理解するのに役立ちます。

ハミルトン閉路問題は次のように要約できると思います。

無向グラフを考えると、ハミルトン閉路は、一度だけのすべての頂点を通過G = (V, E)するツアーです。GG

さて、私がやりたいのは、私の問題をこれに減らすことです。私の問題は：

の重み付き無向グラフG、整数k、および頂点u, v の両方が与えられた場合、 合計の重みが少なくともであるからへGの単純なパスはありますか？Guvk

したがって、ハミルトン閉路問題がNP完全であることを知っているので、この問題をハミルトニアンに還元することにより、この問題もNP完全であることが証明されます。私の問題は、それをハミルトニアンに還元する関数です。

1. 大きな問題は、ハミルトン閉路問題がエッジの重みを処理しないことです。そのため、グラフを重みのないグラフに変換する必要があります。
2. その上、この問題には開始と終了（uとv）が指定されていますが、ハミルトニアンはサイクルを検出するため、開始は終了と同じです。

（1）については、総重量がk未満の単純なパスをすべて取り出したグラフを通過する線に沿って考えています。（2）の場合、これは実際には問題ではないと思います。ハミルトン閉路がある場合、uからvへの単純なパスを切り取ることができるからです。

だから、私の本当の質問は次のとおりです。

1. 私の解決策は私に正しい答えを与えるつもりですか？
2. はいの場合、実際のソリューションでこれらのエッジの1つが必要になる可能性に影響を与えることなく、総重量がk未満の単純なパスを生成するエッジをどのように取り除くことができますか？エッジeがEのサブセットに対して重み<kの単純なパスを生成するために取り出された場合でも、エッジの異なる組み合わせを使用して重み>=kのパスを生成する単純なパスで使用できます。

ありがとう！

ROMAN-SUBSETを次の問題として定義します。

入力：有向グラフG =（V、E）および正の整数k

出力：次のようなVのサブセットRがある場合| R | <= kであり、Gのすべての有向回路にRからの頂点が少なくとも1つ含まれている場合、出力は「TRUE」である必要があります。それ以外の場合は、「FALSE」である必要があります。

頂点被覆（VC）問題がNP完全であると仮定すると、ROMAN-SUBSETもNP完全であることを証明する必要があります。私が理解していることから、これは、VC入力を取得して変更し、それをROMAN-SUBSETアルゴリズムにプラグインするとVC問題の結果が得られることを示すことを意味します。

私は変革を思いつくのに本当に苦労しています。VC入力はグラフGと整数kであり、問​​題は、|R|のようにGのすべてのエッジをカバーするVのサブセットRが存在するかどうかです。<=k。明らかに、RとkはROMからVCまで類似していますが、私の難しさは、すべての有向サイクル（ROMの場合）の1つの頂点がすべてのエッジ（VCの場合）に対応するようにグラフを変換する方法を特定することです。グラフを変更して、VCをROMに削減できることを証明するにはどうすればよいですか？

ありがとう！

これは難しいので、すべての助けが本当に感謝しています!

NP完全であるため、多項式時間で解決できないことはわかっていますが、分析の助けを求めて、どのタイプのNP完全問題に還元されるか、類似の問題を思い出させます.

話は次のようになります。私はn台のトラックでアイスクリーム トラック ビジネスを所有しています。私が配達を行う停留所はmあります。各場所m _iにはp _i人が私を待っています。アイスクリームを買った後、誰もが去ります。p _iは、アイスクリームを求めて並ぶ人が増えるにつれて、時間とともに増加します。

特定の日の利益を最大化するために、トラックを次にどこに送るかをどのように判断できますか?

注意事項:

• 同じ時間に同じ場所に停車する 2 台のトラックは、1 回だけ利益を得ます。つまり、1 台のトラックが到着すると、人々は立ち去ります。
• トラックはある場所から別の場所に移動するのに時間がかかります
• p _iは各停留所で時間とともに増加しますが、一部の停車地は他の停留所よりも速く増加します。つまり、いくつかの場所はモールの近くにあります (場所、場所、場所)

私はこれを複数マシンのスケジューリング問題、巡回販売員の問題、ILP などに還元しようとしましたが、主な問題は、すべての場所でのp _i (つまり、TSP での距離またはスケジューリング問題での仕事の長さ) が常に増加しています。

前もって感謝します！