Turing Reducibilidad de 2 versiones del problema de la satisfacción.

Question

Necesito ayuda con este problema.

Hay 2 versiones del problema de la satisfacción:

[1] Versión de decisión: Determine si una fórmula arbitraria F es satisfactorio o no

[2] Versión de búsqueda: Si una fórmula arbitraria F es satisfactoria, regresa una asignación de valores de verdad a las variables en la fórmula que hace F satisfactorio.Si f es insatisfactorio, devuelve nil.

Muestra que [2] está turando reducible a [1].

Tengo que demostrar que el algoritmo de Oracle de [1] implica que de [2] para decir "[2] está tutando reducible a [1]".

Veo que [2] es solo el algoritmo de Oracle de [1], ya que discrimina la satisfacción de una fórmula arbitraria F.

¿Puede esto significar que el algoritmo de Oracle de [1] implica el de [2]?Si puede, ¿cuál sería la razón?

Answer 1

Cualquier algoritmo que decida la satisfacción de una fórmula también se puede usar para encontrar una asignación para una fórmula satisfactoria:

Si bien no todas las variables están asignadas:

• Elija una variable y elija el valor 0.

• Si la fórmula ya no es satisfactoria, reemplace el valor con 1.