DOI:
https://doi.org/10.14483/22487638.6192Publicado:
2004-01-01Número:
Vol. 7 Núm. 14 (2004): Enero - Junio 2004Sección:
ConcienciasDavis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT
Descargas
Resumen (es)
El esquema de Davis y de Putnam (D&P) se ha estudiado intensivamente durante la última década. Hoy en día, sus buenos resultados empíricos son conocidos. Este artículo se ocupará especialmente de su componente teórico, el cual se ha estudiado relativamente menos hasta este momento. Se propone un algoritmo de D&P que sea lineal para Horn-SAT y cuadrático para 2-SAT; en consecuencia, el algoritmo de D&P diseñado de acuerdo con el problema general SAT corre casi tan rápido (en términos de complejidad) como los algoritmos especializados, diseñados para trabajar exclusivamente con una subclase SAT específica. El algoritmo se ha puesto en ejecución y se ha comparado con solvers muy conocidos para varias subclases de instancias SAT.Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
Licencia
Todos los textos incluidos en la Revista Tecnura están protegidos por derechos de autor. Conforme a la ley, está prohibida su reproducción por cualquier medio, mecánico o electrónico, sin permiso escrito del Comité Editorial. Los textos completos de los artículos son de acceso abierto, es decir, se pueden leer, descargar, copiar, distribuir, imprimir, buscar o vincular. Las opiniones expresadas en los artículos publicados son las de los autores y no coinciden necesariamente con las del Comité Editorial ni las de la administración de la Facultad.