Sobre la Predecibilidad de la Lógica Proposicional Clásica
Autores: Finger, Marcelo; Reis, Poliana M.
Idioma: Inglés
Editor: MDPI
Año: 2013
Acceso abierto
Artículo científico
2013
Sobre la Predecibilidad de la Lógica Proposicional Clásica
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Análisis
Solucionadores SAT
Lógica
Predictibilidad
Distribuciones
Experimentos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
En este trabajo proporcionamos una forma estadística de análisis empírico de los métodos de decisión de la lógica proposicional clásica llamados solucionadores SAT. Este trabajo se percibe como un contraparte empírica de un movimiento teórico, llamado el escándalo perdurable de la deducción, que se opone a considerar la lógica booleana como trivial en ningún sentido. Para ello, estudiamos la predictibilidad de la lógica clásica, que tomamos como la distribución del tiempo de ejecución de su proceso de decisión. Presentamos una serie de experimentos que determinan la distribución de ejecución de los solucionadores SAT y descubrimos un paisaje variable de distribuciones, siguiendo la conocida existencia de una transición de casos fáciles-difíciles-fáciles de fórmulas proposicionales. Encontramos distribuciones claras para las áreas fáciles y las transiciones fácil-difícil y difícil-fácil. Los casos difíciles también se muestran difíciles para la detección de distribuciones estadísticas, lo que indica que varios procesos independientes pueden estar en juego en esos casos.
Descripción
En este trabajo proporcionamos una forma estadística de análisis empírico de los métodos de decisión de la lógica proposicional clásica llamados solucionadores SAT. Este trabajo se percibe como un contraparte empírica de un movimiento teórico, llamado el escándalo perdurable de la deducción, que se opone a considerar la lógica booleana como trivial en ningún sentido. Para ello, estudiamos la predictibilidad de la lógica clásica, que tomamos como la distribución del tiempo de ejecución de su proceso de decisión. Presentamos una serie de experimentos que determinan la distribución de ejecución de los solucionadores SAT y descubrimos un paisaje variable de distribuciones, siguiendo la conocida existencia de una transición de casos fáciles-difíciles-fáciles de fórmulas proposicionales. Encontramos distribuciones claras para las áreas fáciles y las transiciones fácil-difícil y difícil-fácil. Los casos difíciles también se muestran difíciles para la detección de distribuciones estadísticas, lo que indica que varios procesos independientes pueden estar en juego en esos casos.