Reducibilidad de 2 problemas de satisfacción booleana.

Question

Pido ayuda con este problema.

Hay 2 problemas de satisfacción booleana.

Problema $ a $ : Determinación de si una fórmula arbitraria de tamaño $ n $ es $ Satisfecho $ .
Problema $ b $ : Determinación de si una fórmula arbitraria de tamaño $ n-1 $ es $ Satisfecho $ en el que $ n $ es un entero positivo $ \ ge 2 $

Demuestra que $ a $ puede ser solevable si $ b $ es soluble.

Supongo que la solución mostrará que $ a $ está reducible a $ b $ . Significa que tengo que mostrar el algoritmo de Oracle de $ b $ deriva el algoritmo de Oracle de $ a $ .

Como ves, la fórmula arbitraria de $ b $ es $ n-1 $ , pero El de $ a $ es $ n $ . ¿Cómo puedo suponer que conllevar el algoritmo de Oracle sobre $ a $ desde el oráculo de $ b $ , que ¿Determina la fórmula de un tamaño 1 menor que el de $ b $ ?

Answer 1

Problema A es reducible al problema B de la siguiente manera:

• Elige una variable en el problema A y configúralo para 0
• Ahora tenemos una fórmula de tamaño N-1, si está satisfecho con B, luego devuelva Satisfecho
• de lo contrario, elija un problema de nuevo y configure la variable a 1
• Ahora tenemos una fórmula de tamaño N-1 nuevamente, si está satisfecho con B, luego regrese satisfecho más de devolución insatisfecho

En otras palabras: dividir el problema A en dos problemas B usando cualquier variable.Si B dice insatisfactorio tanto para 0 como para 1, entonces es insatisfactorio.Si dice satisfactorio por al menos uno de los dos, entonces es satisfactorio.