サブセット推論NP完了？</p> <p>がありますあなたがそれらを見ることができませんN.</p> <p>番号1〜Nのコインですが、フォームのそれらについてMの事実を与えられている：</p> <pre><code>struct Fact { set<int> positions int num_heads } </code></pre> <p><code>positions</code>

Question

は、次のような問題を考えてみましょうコインのサブセットを識別し、num_headsは、そのサブセット内のヘッドであるコインの数である。

これらのM個の事実を考えれば、できるだけ多くのヘッドを開発する必要があります。

この問題はNP完了ですか？はいの場合、削減額はいくらですか？いいえ、多項式時間の解は何ですか？例えば

：事実と一致して、ほとんどのヘッドと

N = 5 
M = 3 
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head 
fact2 = { {4}, 0 } // Coin 4 is a tail 
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads 

設定は次のとおりです。

T H H T H 

だから、答えは3頭です。

Answer 1

あなたは3-SATの問題があるとしましょう。その問題のすべてのブール変数vを2つのコインにマッピングできます。それらを「真（v）」と「偽（v）」と呼んでください。その考え方は、3-SAT問題の解法のvが真であれば、「真（v）」は頭であることである。さもなければ「偽（v）」は頭部である。すべてのためにあなたは、この後、あなたはコイン制約

{t/f(l1), t/f(l2), t/f(l3)} has at least 1 heads 

にリテラルのL1、L2、L3

l1 or l2 or l3 

と3-SATの句を翻訳することができ

{true(v), false(v)} has 1 heads, and has 1 tails 

をコイン制約を追加V

ここで、l1が肯定（否定されていない）または否定（否定）されているかどうかによって、t/f（l1）は 'true（l1）'または 'false 「少なくとも1つのヘッド」は直接表現できないので、「少なくとも1つのヘッド」がコインの問題に実装できることを示す必要があります。これは次のデバイスで行うことができます。 C1、C2、C3を3つのコインとし、「少なくとも1つは頭である」という制約を述べたいとします。他の三つのコインX1、X2、X3を作成し、制約で

{X1, X2, X3, C1, C2, C3} has 4 heads 

が、X1、X2、X3に他の制約を置きます。この制約は、C1、C2、C3の少なくとも1つが頭である場合にのみ満たされる。硬貨X1..3を使用して残りの必要な頭部を提供することができる。

この削減では、問題の「ヘッドの最大数」の側面はまったく使用されないことに注意してください。 3-SAT式が満たされない場合、ブール変数を表すコインの頭/尾の状態を選択することは明らかに不可能である。

これは、NP-hardであることを示す、3-SATからあなたのコインの問題までの多項式削減です。それがNP完全であることを示すには、多項式時間QEDであなたの硬貨問題の解を調べることができます。

Answer 2

One-in-three 3SATは、あなたの問題の決定版（すべての構成はありますか？最大化バージョンはNP-ハードです（ただし、決定の問題ではないので完全ではありません）。満足できる設定でなければならない約束バージョンですら、決定還元の出力に追加します。そのコインが頭であり、他のすべてが尾である、悪い追加ソリューションを作成します。

Answer 3

パーフェクトマッチングでは、エッジをコインとして表現すると、グラフの各頂点に対して、偶然のエッジの1つだけが頭であることを示すファクトが作成されます。コインに解がある場合にのみ、元のグラフの完全一致が存在します。