juanreutter
commented
3 years ago Hola Vicente, claro!
Piensa en lo siguiente: dada una formula phi con rango de cuantificacion k, el espacio de busqueda para SAT es infinito, y esa es mas menos la razón de por qué es indecidible. Ahora. este espacio infinito, quizá se podría reducir de alguna forma, aprovechando la idea de que todas las estructuras que jueguen en k rondas van a ser "equivalentes" en cuanto al valor de verdad de phi.
Creo que lo relevante es principalmente el teorema de EF, el resto ya es ponerse a pensar nomás :)
On Mon, 1 Nov 2021 at 20:05, Vicente Calisto @.***> wrote:
Hola profesor,
Quería consultar cómo podríamos realizar la pregunta 2, ya que no logro encontrar una forma para demsotrar la decidibilidad de un lenguaje utilizando Juegos de EF (los cuales utilizábamos para la expresividad en LPO).
Sería de utilidad cualquier tipo de pista (clases relevantes, capítulos del libro de Leonid Libkin, etc.)
Desde ya muchas gracias 😃
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android.
VicenteVicente
Hola profesor,
Quería consultar cómo podríamos realizar la pregunta 2, ya que no logro encontrar una forma para demostrar la decidibilidad de un lenguaje utilizando Juegos de EF (los cuales utilizábamos para la expresividad en LPO).
Sería de utilidad cualquier tipo de pista (clases relevantes, capítulos del libro de Leonid Libkin, etc.)
Desde ya muchas gracias 😃