Turing Reducibilidad de 2 versiones del problema de la satisfacción.
-
29-09-2020 - |
Pregunta
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?
Solución
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.