5

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

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

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

struct Fact
{
    set<int> positions
    int num_heads
}

positionsコインのサブセットを識別し、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つの頭です。

4

3 に答える 3

2

3-SATの問題があるとしましょう。その問題のすべてのブール変数vを2つのコインにマップできます。それらを「true（v）」および「false（v）」と呼びます。考え方は、3-SAT問題の解のvが真である場合、「true（v）」が頭であるということです。それ以外の場合、「false（v）」はヘッドです。すべてのvに対して、コイン制約を追加します

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

この後、リテラルl1、l2、l3を使用して3-SAT句を翻訳できます。

l1 or l2 or l3

コイン制約に

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

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

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

ただし、X1、X2、X3には他の制約はありません。この制約は、C1、C2、C3の少なくとも1つがヘッドである場合にのみ満たされます。コインX1..3は、残りの必要なヘッドを提供するために使用できます。

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

これは、3-SATからコインの問題への多項式縮小であり、NP困難であることを示しています。NP完全であることを示すために、コインの問題の解が多項式時間QEDでチェックできることを確認してください。

于 2012-05-17T15:46:19.737 に答える
1

3分の1の3SATは、問題の決定バージョン（構成は存在しますか？）に簡単に還元されます。これは、NPに簡単に含まれています。最大化バージョンはNP困難です（ただし、決定問題ではないため完全ではありません）。満足のいく構成が必要なPromiseバージョンでも、すべてのサブセットに表示される1つの追加コインを決定削減の出力に追加します。そのコインが表であり、他のすべてが裏である、1つの悪い余分な解決策を作成します。

于 2012-05-17T16:06:23.243 に答える
0

完全なマッチングを使用すると、この問題を簡単に減らすことができます。エッジをコインとして表します。グラフ内のすべての頂点について、偶発的なエッジの1つがヘッドであることを規定するファクトを作成します。元のグラフの完全な一致は、コインに解決策がある場合にのみ存在します。

于 2012-05-18T07:08:29.227 に答える