$⊕P$ – $⊕2SAT$の完全性

$⊕2SAT$ – $ 2 $ – $ CNF $ formula $ oplus P
$の解の数のパリティは完全ですか?

これは、Valiantの2005年の論文に未解決の問題として記載されています。 https://link.springer
.com/content/pdf/10.1007%2F11533719.pdf
これは解決されましたか?

P $で$⊕2SATならば、どんな影響がありますか?

ベストアンサー

Fabenによって$ $ oplus P $ -completeであることが示されています。

https://arxiv.org/pdf/0809.1836.pdf

Thm 3.5を参照してください。独立した集合を数えることは、2CNFを単調にするための解を数えることと同じです。

返信を残す

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