Turning réductibilité de 2 versions du problème de satisfabilité

Question

J'ai besoin d'aide avec ce problème.

Il y a 2 versions du problème de satisfaction:

[1] Version de décision: Déterminez si une formule arbitraire F est satisfaisable ou non

[2] Version de recherche: Si une formule arbitraire F est satisfaite, retour une affectation de valeurs de vérité aux variables dans la formule qui fait F satisfaisable.Si F est insatisfaite, retournez nulle.

montre que [2] est en train de traiter réductible à [1].

Je dois prouver que l'algorithme Oracle de [1] implique que [2] à dire "[2] est en train de traiter réductible à [1]".

Je vois que [2] est juste l'algorithme Oracle de [1] puisqu'il discrimine la satisfaction d'une formule arbitraire f.

Cela signifie-t-il que l'algorithme Oracle de [1] implique celui de [2]?Si peut, quelle serait la raison?

Answer 1

Tout algorithme qui décide que la satisfaction d'une formule peut également être utilisé pour trouver une affectation pour une formule satisfaisante:

Bien que toutes les variables ne soient pas attribuées:

• Choisissez une variable et choisissez Valeur 0.

• Si la formule n'est plus satisfaite, remplacez la valeur avec 1.