DOI:

https://doi.org/10.14483/22487638.6192

Publicado:

2004-01-01

Número:

Vol. 7 Núm. 14 (2004): Enero - Junio 2004

Sección:

Conciencias

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 Autores/as Métricas disponibles Cómo citar

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., 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, 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: 5 nov. 2024.

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, Gonzalo, y Nelson 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 noviembre 5, 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]. 1 de enero de 2004 [citado 5 de noviembre de 2024];7(14):57-6. Disponible en: https://revistas.udistrital.edu.co/index.php/Tecnura/article/view/6192

Descargar cita

Visitas

129

Dimensions


PlumX


Descargas

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

Licencia

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.