充足可能性の問題の2つのバージョンの抑制性

Question

この問題を助ける必要があります。

充足可能性の問題の2つのバージョンがあります：

[1]決定バージョン：任意の式fがあるかどうかを判断する 満足できるかどうか

[2]検索バージョン：任意の式fが満足できる場合は、返品 fを作成する式の変数への真理値の割り当て 満足できる。fが満足のいく場合は、NILを返します。

[2]は[1]に還元可能なチューリングであることを示しています。

[1]のOracleアルゴリズムが[2]のOracle Algorithmが[2]「[2]が[1]に廃止されていることを証明することを証明する必要があります。

[2]は、任意の式fの充満性を判定するので、[1]のOracleアルゴリズムであることがわかりました。

これは[1]のOracleアルゴリズムが[2]のOracleアルゴリズムを伴うことができますか？可能であれば、理由は何でしょうか？

Answer 1

式の満足度を決定する任意のアルゴリズムを、満足できる式のための割り当てを見つけることもできます。

すべての変数が割り当てられていないが：

• 変数を選び、値0を選ぶ

• 式が満足できなくなった場合は、値を1に置き換えます。