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
Escalada Imaz, G., y Becerra Correa, N. (2004). Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura, 7(14), 57–67. https://doi.org/10.14483/22487638.6192
ACM
[1]
Escalada Imaz, G. y Becerra Correa, N. 2004. Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura. 7, 14 (ene. 2004), 57–67. DOI:https://doi.org/10.14483/22487638.6192.
ACS
(1)
Escalada Imaz, G.; Becerra Correa, N. Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura 2004, 7, 57-67.
ABNT
ESCALADA IMAZ, G.; BECERRA CORREA, N. Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura, [S. l.], v. 7, n. 14, p. 57–67, 2004. DOI: 10.14483/22487638.6192. Disponível em: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192. Acesso em: 21 mar. 2023.
Chicago
Escalada Imaz, Gonzalo, y Nelson Becerra Correa. 2004. «Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT». Tecnura 7 (14):57-67. https://doi.org/10.14483/22487638.6192.
Harvard
Escalada Imaz, G. y Becerra Correa, N. (2004) «Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT», Tecnura, 7(14), pp. 57–67. doi: 10.14483/22487638.6192.
IEEE
[1]
G. Escalada Imaz y N. Becerra Correa, «Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT», Tecnura, vol. 7, n.º 14, pp. 57–67, ene. 2004.
MLA
Escalada Imaz, G., y N. Becerra Correa. «Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT». Tecnura, vol. 7, n.º 14, enero de 2004, pp. 57-67, doi:10.14483/22487638.6192.
Turabian
Escalada Imaz, Gonzalo, y Nelson Becerra Correa. «Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT». Tecnura 7, no. 14 (enero 1, 2004): 57–67. Accedido marzo 21, 2023. https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192.
Vancouver
1.
Escalada Imaz G, Becerra Correa N. Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura [Internet]. 1 de enero de 2004 [citado 21 de marzo de 2023];7(14):57-6. Disponible en: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192
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.
