Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Sobre fórmulas CNF irredundantes con respecto a la propagación de la cláusula unitaria

Created by
  • Haebom

Autor

Petr Savick y

Describir

Este artículo define dos fórmulas CNF que se comportan de forma idéntica bajo Propagación de Cláusula Unitaria (UCP) como ucp-equivalentes, y define una fórmula que no es ucp-equivalente a la fórmula original sin importar qué cláusula se elimine como ucp-irredundante. Según resultados de investigaciones previas, la razón entre el tamaño de una fórmula ucp-irredundante y el tamaño de la fórmula ucp-equivalente más pequeña es como máximo $n^2$ (n es el número de variables). En este artículo, mostramos que el límite superior general de la razón no puede ser menor que este valor dando un ejemplo de una fórmula ucp-irredundante cuyo tamaño es $\Omega(n/\ln n)$ veces mayor que el de la fórmula ucp-equivalente más pequeña para una función de Horn definida simétrica.

Takeaways, Limitations

Takeaways: Mejora el límite superior existente ($n^2$) al proporcionar un límite inferior para la razón de tamaño de la fórmula ucp-irredundante y la fórmula ucp-equivalente más pequeña. Respalda el resultado teórico con un ejemplo concreto de una función de Horn definida simétrica.
Limitations: La cota inferior presentada corresponde a una función específica (una función de Horn definida simétrica) y no proporciona una cota inferior para la fórmula general de la CNF. Se requieren estudios más generales.
👍