1

k 個の単項節と 2 つの節しかない SAT インスタンスの複雑さは?

この結果の論文を見つけたいと思います.. 問題が少し異なる論文を 1 つ見つけました。すべての変数は最大で 2 回表示されます ...

4

2 に答える 2

0

あなたの問題にはcomplexity in O(n)where がありn is the total size of clausesます。

K 単項句があります。これらの K 単項句は、変数のサブ代入と見なすことができます。これらの単項節を尊重しない場合、解決策が見つからないことは確かです (存在する場合)。

例を挙げて問題を見てみましょう。目標は の値を見つけることですvariables。

 variables = _ _ _ _ _ _ _ _
 problem   = 
              x1                 AND
              x4                 AND
              x7                 AND
             -x8                 AND
             -x5                 AND
              x2                 AND
              x3 OR  -x4 OR x5   AND
              x6 OR  -x1 OR x8

 with K = 5.

単項節は値を に伝播するためvariables、この問題は基本的に と同じです。

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 OR  -x4 OR  x5  AND
              x6 OR  -x1 OR  x8
 with K = 0.

(これを取得するために、線形時間操作を行いました)。

また、x4、x5、x1、x8 の値は既にわかっているため、この問題は次のようになります。

 variables = x1 x2 _ x4 -x5 _ x7 -x8
 problem   = 
              x3 AND
              x6
 with K = 0.

(これを取得するために、再び線形時間操作を行いました)。

そして、最初の操作と同じ種類の関数を呼び出すことで、以下を取得します。

 variables = x1 x2 x3 x4 -x5 x6 x7 -x8
 problem   = 
              true.
 with K = 0.

(この結論を得るために、再び線形時間操作を行いました)。

これにより、最終的な解が得られます。variables = x1 x2 x3 x4 -x5 x6 x7 -x8 ご覧のとおり、線形時間操作を使用してのみ解を見つけることができます。

于 2015-07-28T11:16:07.593 に答える
0

私が正しく理解していれば、これは句の全長で線形時間のようです。

単項節は、部分的な変数代入 τ を即座に強制します。2 つの節のいずれかが τ の下で充足可能でない (空である) 場合、または一部の単位節が矛盾している場合、インスタンスは充足不可能です。それ以外の場合、インスタンスは、2 つの節が τ の下で単位であり補完的である場合、つまり x̅ と x である場合にのみ充足できません。

于 2015-07-27T18:53:07.267 に答える