Estudio Computacional de la Definibilidad por Fórmulas de Primer Orden sin Cuantificadores | Defensa de Trabajo Especial de la Licenciatura en Ciencias de la Computación

Día: miércoles 26 de febrero de 2025

Hora: 14:30 h

Lugar: Aula Magna | FAMAF

Resumen: En este trabajo estudiamos la complejidad computacional del problema de decisión de definibilidad. Dadas una estructura A y un conjunto R de n-uplas sobre el universo de A, el problema de definibilidad de R en A consiste en determinar si existe una fórmula de primer orden cuya interpretación en A coincide con R. Abordamos aquí el problema de definibilidad por fórmulas abiertas (sin cuantificadores) y por fórmulas abiertas positivas (también sin ocurrencias de los símbolos de negación, de implicación, y de doble implicación). Mostramos que, cuando la estructura A tiene solamente relaciones unarias o solamente funciones unarias, los problemas están en la clase de complejidad P. Refinamos estos resultados para estructuras relacionales, y concluimos que tanto el problema de definibilidad abierta como el de definibilidad abierta positiva para este tipo de estructuras son decidibles en espacio logarítmico. Complementamos estos resultados demostrando que distintas restricciones del problema de definibilidad abierta para álgebras unarias están también en L. Además probamos que los demás casos del problema (en su versión algebraica) son difíciles para NL. Por último, demostramos que el problema de definibilidad abierta para álgebras con una cantidad arbitraria de funciones unarias es logarítmicamente equivalente al problema para álgebras con dos funciones unarias.