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

Autores/as

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

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.

Biografía del autor/a

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.

Cómo citar

APA

Escalada Imaz, G., & 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: 10 may. 2021.

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 mayo 10, 2021. 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 10 de mayo de 2021];7(14):57-6. Disponible en: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192

Descargar cita

Visitas

84

Dimensions


PlumX


Descargas

Los datos de descargas todavía no están disponibles.