重复2个布尔可满足性问题

Question

我求出一些问题。

有2个布尔可满足性问题。

问题 $ a $ ：确定大小的任意公式 $ n $ 是 $满足$ 。

问题 $ b $ ：确定大小的任意公式 $ n-1 $ $满足$ 其中 $ n $ 是一个正整数 $ \ ge 2 $

证明 $ a $ 如果 $ b $ 是可解决的。

我猜解决方案将显示 $ a $ 是为了 $ b $ 。这意味着我必须显示 $ b $ 派生 $ a $ 的Oracle算法的Oracle算法。

如您所见， $ b $ 的任意公式是 $ n-1 $ ，但 $ a $ 是 $ n $ 。 如何假设从 $ b $ 的Oracle上，概述Oracle算法关于 $ a $ 确定比 $ b $ ？

的公式

Answer 1

问题A以以下方式将问题B还原：

• 在问题A中选择一个变量并将其设置为 0
• 现在我们有一个大小的公式N-1，如果与B的满足，则返回满足的
• else，再次选择问题，并将变量设置为1
• 现在我们再次有一个大小的N-1公式，如果与B的满足，那么返回满足的其他返回返回不匹配

换句话说：使用任何变量将问题A分为两个问题b。如果B对0和1表示不挑离，那么它就不可能。如果它对两个中的至少一个表示满足，那么它是满意的。