Turning réductibilité de 2 versions du problème de satisfabilité
-
29-09-2020 - |
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?
La solution
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.