computer-science - ひねりを加えた 3-cnf-sat 質問

Question

3-cnf-sat 問題を次のように変更した場合:
各 c _iについて、 c _i = -x _i1 OR -x _i2 OR x _i3は、変数の 1 つだけが否定なしで表示されることを意味します。
また、x の一部 (またはすべて) に値 (0 または 1) が与えられます。
多項式時間で問題を解決できる必要があります (問題を満たす x の値を見つけるか、問題が満たされないことを証明します)。

1. この問題を解決する多項式実行時間アルゴリズムは何ですか?
2. 多項式時間で実行されることを証明します。

ヒント: c _i = -x _i1 OR -x _i2 OR x _{i3が c = (x i1} AND -x _i2 ) -> x _i3と等しいことを示す

Answer 1

あなたが説明する数式は、ホーンの数式のサブセットです。したがって、充足可能性の問題はホーンの充足可能性より難しくなく、同じ線形時間解を認めます。