Récidité de 2 problèmes de satisfaction booléens

Question

Je vous demande de l'aide avec ce problème.

Il y a 2 problèmes de satisfaction booléens.

problème $ A $ : déterminer si une formule arbitraire de taille $ n $ est $ satisfaisable $ .
Problème $ B $ : déterminer si une formule arbitraire de taille $ n-1 $ est $ satisfaisable $ dans lequel $ n $ est un entier positif $ \ ge 2 $

prouver que $ a $ peut être résoluble si $ B $ est solvable.

Je suppose que la solution montrerait que $ a $ est en train de réductible à $ B $ . Cela signifie que je dois montrer l'algorithme Oracle de $ B $ dérive l'algorithme Oracle de $ a $ .

Comme vous le voyez, la formule arbitraire de $ b $ est $ n-1 $ , mais Celui de $ a $ est $ n $ . Comment puis-je supposer impliquer l'algorithme Oracle sur $ A $ de l'oracle de $ B $ , qui détermine la formule de taille de 1 moins que celle de $ B $ ?

Answer 1

Problème A est réductible au problème B de la manière suivante:

• Choisissez une variable dans le problème A et la définir à 0
• Nous avons maintenant une formule de taille N-1, si satisfaisible avec B puis retourne satisfiables
• ailleurs, choisissez à nouveau le problème et définissez la variable à 1
• Nous avons maintenant une formule de taille N-1 à nouveau, si satisfaisable de B puis de retourner satisfaisant sans assurance

En d'autres termes: diviser le problème A en deux problèmes B à l'aide de toute variable.Si B indique insatisfaite pour 0 et 1, il n'est pas satisfait.S'il est dit satisfaisable pour au moins un des deux, il est satisfait.