LogspaceでのXOR 3-SATの解決の結果は何ですか?

XOR数式

接続変数$ wedge $(AND)と$ oplus
$(XOR)を持つ論理式を考えてみましょう。このようなブール式は、XOR SATが$ oplus $
-clausesの結合である場合、その有効なインスタンスです。 $ oplus $には、$ oplus
$で連結されたリテラルが含まれています。

例数式:

wedge( bar {v_1} oplus v_2) wedge( bar {v_2} oplus v_3
oplus bar {v_4})$(v_1 oplus bar {v_2} oplus

決定の問題

名前: XOR 3-SAT

     

入力:各節に3つのリテラルが含まれている$ oplus $
-clausesの結合であるブール式です。

     

質問:数式を満たす変数に代入が存在しますか?

その他の背景

XOR SATは、$ mathbb {Z} _2 $以上の方程式の系を解くことに還元することができます。これは、すべての$
oplus $節が方程式と考えることができるからです。結果として、XOR
SATは、ガウス消去を使用して多項式時間で解くことができます。

さらに、XOR 2-SATは、無向グラフの到達可能性を解決するために削減することができる。これは、2つのリテラルを持つすべての$
oplus $句が、無向グラフのエッジを定義するためです。結果として、XOR
2-SATは、無向グラフの到達可能性がlogspaceで解決可能であるため(SL =
Lであるため)、logspaceで解くことができます。

質問

(1)XOR 3-SATはログスペースで解決できますか?

     

(2)ログスペースにXOR 3-SATを解決した結果はありますか?

     

(3)たとえば、これはXOR $ k $ -SATが   ログスペース?

ベストアンサー

https://www.sciencedirect.com/science/article/pii/S0022000008001141をご覧ください。
Allender et al。による「充足可能性問題の複雑さ:Refining Schaeferの定理」あなたの質問に答える:

(1)オープン

(2)$ oplus L = L $

(3)はい

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です