6

いくつかの有限集合があるとしましょう:A, B, ..., K

A1, A2, ... AnA のサブセットであるものもあります。B1, B2, ... Bnこれは B などの部分集合です。

Sデカルト積であるとしましょうA x B x ... x K

のSnデカルト積です。An x Bn x ... x Kn

Snすべての結合がと等しいかどうかを効率的に判断するアルゴリズムはありSますか?

編集

この質問は、Theoretical Computer Scienceフォーラムでも行いました。答えは、問題が coNP 完全であることを証明します。回答の作成者がここに投稿したい場合は、賞金を授与するために質問を開いたままにしています。

4

2 に答える 2

3

問題は coNP-Complete であるため、それを解決するための効率的なアルゴリズムはありません。

3SATがこの問題の補数に還元できることを示します (すべての S iの和集合が Sに等しくないかどうかをチェックします)。

変数 a、b、...、k およびブール式を使用した 3SAT 問題を考えてみましょう

        f = c 1 ∧ c 2 ∧ ... ∧ c n

どこ

        c i = x i,1 ∨ x i,2 ∨ x i,3

x i,jはリテラル (変数または変数の否定) です。

A = B = C = ... = K = { true, false } と設定します。

A iを

  • { false } c iに変数 a が含まれる場合
  • { true } c iが変数 a の否定を含む場合
  • { true, false } もし c iが aに言及していないなら

同様に、すべての 1 ≤ i ≤ nの B iから K iまで。

タプル (a, b, ..., k) ∈ S i = A i ⨯ B i ⨯ ... ⨯ K iは、 c iのすべてのリテラルが否定されるため、 c iを満たしません。

タプル (a, b, ..., k) ∈ S 1 ⋃ S 2 ⋃ ... ⋃ S nを考えてみましょう。これらのタプルは、少なくとも 1 つの Si に属しているため、 ciを満たさず、したがってfを満たさない。

S 1 ⋃ S 2 ⋃ ... ⋃ S nが S = A ⨯ B ⨯ ... ⨯ K に等しい場合、すべてのタプルが f を満たさないため、f は満たされない。同様に、共用体が S に等しくない場合、f を満たすタプルが存在することを示すことができます。

したがって、3SAT は元の問題の補数に縮小できます。しかし、元の問題の補数は NP にあります。これは、特定のタプルが和集合に含まれていないかどうかのテストが多項式時間で実行できるためです。つまり、元の問題の補数が NP-Complete であり、元の問題自体が coNP-Complete です。

于 2013-08-20T07:00:00.317 に答える