algorithm - 2-充足可能性問題-一意の真理割り当てが存在するかどうか

Question

2-SAT問題の延長である問題があります。標準の2-SAT問題では、選択した頂点の順序に依存する真理の割り当てを見つけることができます。式が充足可能な真理代入が1つだけ（つまり、組み合わせが1つだけ）存在するかどうかを確認したいと思います。リテラルの数は100000にすることができます。1つの方法は、考えられるすべての真理の割り当てを見つけて、それらが異なる場合はそれらを比較することです。しかし、問題は比較ごとにあり、100000個の値（リテラルなし）を比較する必要があります。効率的な方法はありますか？

Answer 1

Feder (1994) は、与えられた 2 充足可能性インスタンスに対するすべてのソリューションを効率的にリストするアルゴリズムについて説明しています。この記事には、割り当ての数をカウントするアルゴリズムの引用もありますが、2 つの割り当てをリストするだけで済み、より効率的である可能性があります。