Riduzione delle 2 versioni del problema della soddisfazione

Question

Ho bisogno di aiuto con questo problema.

.

Ci sono 2 versioni del problema della soddisfattiva:

[1] Versione decisione: determinare se una formula arbitraria f sia Soddisfare o meno

[2] Versione di ricerca: se una formula arbitraria F è soddisfatta, il ritorno Un'assegnazione di valori di verità alle variabili nella formula che fa f SOSTABILE.Se F è insoddisfacente, restituisce Nil.

Mostra che [2] è riducibile a [1].

Devo dimostrare che l'algoritmo Oracle di [1] comporta quello di [2] dire "[2] è riducibile a [1]".

Vedo che [2] è solo l'algoritmo Oracle di [1] poiché discrimina la soddisfazione di una formula arbitraria f.

Può questo significa che l'algoritmo Oracle di [1] implica quello di [2]?Se può, quale sarebbe la ragione?

Answer 1

Qualsiasi algoritmo che decide che la soddisfabilità di una formula può anche essere utilizzata per trovare un incarico per una formula soddisfatta:

Mentre non sono assegnate tutte le variabili:

.

• scegli una variabile e scegliere il valore 0.

• Se la formula non è più soddisfatta, sostituire il valore con 1.