DOI:

https://doi.org/10.14483/22487638.6192

Published:

2004-01-01

Issue:

Vol. 7 No. 14 (2004): Enero - Junio 2004

Section:

Conciencias

Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT

Authors

  • Gonzalo Escalada Imaz Institute of Scientific Research Spanish Council
  • Nelson Becerra Correa Institute of Scientific Research Spanish Council

Downloads

Abstract Authors Available Metrics How to Cite

Abstract (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.

Author Biographies

Gonzalo Escalada Imaz, Institute of Scientific Research Spanish Council

Físico. Ingeniero Informatico. PhD en Ciencias de la Computación. Professor of the Artificial Intelligence Research, Institute of Scientific Research Spanish Council. Barcelona.

Nelson Becerra Correa, Institute of Scientific Research Spanish Council

Ingeniero de sistemas. Magíster en ingeniería de Sistemas. Candidato a doctor en Inteligencia Artificial. Docente de la Universidad Distrital Francisco José de Caldas adscrito a la Facultad Tecnológica. Investigador de Artificial Intelligence Research Institute of Scientific Research Spanish Council CSIC.  Barcelona.

How to Cite

APA

Escalada Imaz, G., and 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. and Becerra Correa, N. 2004. Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT. Tecnura. 7, 14 (Jan. 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, Gonzalo; BECERRA CORREA, Nelson. 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: 17 jul. 2024.

Chicago

Escalada Imaz, Gonzalo, and 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. and 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 and N. Becerra Correa, “Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT”, Tecnura, vol. 7, no. 14, pp. 57–67, Jan. 2004.

MLA

Escalada Imaz, Gonzalo, and Nelson Becerra Correa. “Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT”. Tecnura, vol. 7, no. 14, Jan. 2004, pp. 57-67, doi:10.14483/22487638.6192.

Turabian

Escalada Imaz, Gonzalo, and Nelson Becerra Correa. “Davis y Putman es lineal para Horn-SAT y cuadrático para 2-SAT”. Tecnura 7, no. 14 (January 1, 2004): 57–67. Accessed July 17, 2024. 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]. 2004 Jan. 1 [cited 2024 Jul. 17];7(14):57-6. Available from: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192

Download Citation

Visitas

103

Dimensions


PlumX


Downloads

Download data is not yet available.

License

Esta licencia permite a otros remezclar, adaptar y desarrollar su trabajo incluso con fines comerciales, siempre que le den crédito y concedan licencias para sus nuevas creaciones bajo los mismos términos. Esta licencia a menudo se compara con las licencias de software libre y de código abierto “copyleft”. Todos los trabajos nuevos basados ​​en el tuyo tendrán la misma licencia, por lo que cualquier derivado también permitirá el uso comercial. Esta es la licencia utilizada por Wikipedia y se recomienda para materiales que se beneficiarían al incorporar contenido de Wikipedia y proyectos con licencias similares.