Riduzione di 2 problemi di soddisfazione booleana
-
29-09-2020 - |
Domanda
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 $ ?
Soluzione
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.