Redutibilidade de 2 problemas de satisfabilidade booleana

Question

Eu imploro alguma ajuda com este problema.

.

Existem 2 problemas de satisfabilidade booleana.

problema $ a $ : determinar se uma fórmula arbitrária de tamanho $ n $ é $ satisfável $ .
Problema $ B $ : Determinando se uma fórmula arbitrária de tamanho $ n-1 $ é $ satisfável $ em que $ n $ é um inteiro positivo $ \ GE 2 $

Prove que $ a $ pode ser solucionável se $ b $ é solublível.

Eu acho que a solução seria mostrando que $ a $ é redutível para $ B $ . Isso significa que eu tenho que mostrar o algoritmo do Oracle de $ b $ deriva o algoritmo Oracle de $ a $ .

Como você vê, a fórmula arbitrária de $ b $ é $ N-1 $ , mas A da $ a $ é $ n $ . Como posso supor que implique o algoritmo Oracle sobre $ a $ do oracle de $ B $ , que é determinar a fórmula de 1º tamanho do que a da $ B $ ?

Answer 1

problema A é reduzido ao problema B de seguinte maneira:

• Escolha uma variável em Problema A e configure-a para 0
• agora temos uma fórmula de tamanho N-1, se satisfatório com B, em seguida, retornar satisfatório
• mais, escolha o problema novamente e defina a variável para 1
• agora temos uma fórmula de tamanho n-1 novamente, se satisfatório com B, em seguida, retornar satisfaivelmente o retorno de retorno

Em outras palavras: Dividir o problema em dois problemas b usando qualquer variável.Se B diz insatisfatório para 0 e 1, então é insatisfatório.Se ele disser satisfatório por pelo menos um dos dois, então é satisfatório.