Riduzione di 2 problemi di soddisfazione booleana

Question

Chiedo aiuto a questo problema.

.

Ci sono 2 problemi di soddisfazione booleana.

PROBLEMA $ A $ : Determinazione se una formula arbitraria di dimensioni $ N $ è $ $ soddisfavole $ .
Problema $ B $ : determinare se una formula arbitraria di dimensioni $ N-1 $ è $ Soddisfazione $ in quale $ N $ è un numero intero positivo $ \ Ge 2 $

Dimostrare che $ A $ può essere risolvibile se $ B $ è solvibile.

Immagino che la soluzione mostrerebbe quella $ A $ è riducibile a $ B $ . Significa che devo mostrare l'algoritmo Oracle di $ B $ deriva l'algoritmo Oracle di $ a $ .

Come vedi, la formula arbitraria di $ B $ è $ n-1 $ , ma Quello di $ A $ è $ N $ . Come posso prevedere di comportare l'algoritmo Oracle circa $ A $ dall'oracolo di $ B $ , che sta determinando la formula di 1-meno dimensione rispetto a quella della $ B $ ?

Answer 1

Problema A è riducibile al problema B nel modo seguente:

.
• scegli una variabile in problema a e impostalo 0
• Ora abbiamo una formula di taglia N-1, se soddisfaggiabile con B quindi restituire lo Soddisfazione
• Altrimenti, selezionare un problema di nuovo e imposta la variabile su 1
• Ora abbiamo una formula di taglia N-1 di nuovo, se soddisfaggiabile con B quindi restituire l'altro insaputabile restituire insoddisfavibile

In altre parole: Dividi problemi A in due problemi B usando qualsiasi variabile.Se B dice insoddisfable sia per 0 e 1, allora è insoddisfacente.Se si dice sia soddisfatti per almeno uno dei due, allora è soddisfacente.