A randomized algorithm for solving the satisfiability problem

In spite of the NP-completeness of the satisfiability decision problem (SAT problem), many researchers have been attracted by it because SAT has many applications in Artificial Intelligence. This paper presents a randomized David-Putnam based algorithm (RSAT) which solves this problem. Instead of se...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Cecchi, Laura
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 1997
Materias:
Ciencias Informáticas
complete problems
NP
Satisfiability problem
ARTIFICIAL INTELLIGENCE
Algorithms
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24079
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-24079
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
complete problems
NP
Satisfiability problem
ARTIFICIAL INTELLIGENCE
Algorithms
spellingShingle Ciencias Informáticas
complete problems
NP
Satisfiability problem
ARTIFICIAL INTELLIGENCE
Algorithms
Cecchi, Laura
A randomized algorithm for solving the satisfiability problem
topic_facet Ciencias Informáticas
complete problems
NP
Satisfiability problem
ARTIFICIAL INTELLIGENCE
Algorithms
description In spite of the NP-completeness of the satisfiability decision problem (SAT problem), many researchers have been attracted by it because SAT has many applications in Artificial Intelligence. This paper presents a randomized David-Putnam based algorithm (RSAT) which solves this problem. Instead of selecting the next literal to be set true or false through a heuristic selection rule, RSAT does it through a random algorithm. RSAT not only improves the well-know Davis-Putnam Procedure that has been implemented with a heuristic selection rule, but avoids the incompleteness problem of the local search algorithms as well. RSAT is described in detail and it is compared with the heuristic based Davis-Putnam algorithm HDPP. We discuss the main features of the RSAT implementation and we especially analyze the random number generator features. Although the scope of the experiment is bound by the number of variables, our results indicate that the heuristic can be guessed by a random number generator and even improved. Empirical analysis that support the final conclusions are shown.
format Objeto de conferencia
Objeto de conferencia
author Cecchi, Laura
author_facet Cecchi, Laura
author_sort Cecchi, Laura
title A randomized algorithm for solving the satisfiability problem
title_short A randomized algorithm for solving the satisfiability problem
title_full A randomized algorithm for solving the satisfiability problem
title_fullStr A randomized algorithm for solving the satisfiability problem
title_full_unstemmed A randomized algorithm for solving the satisfiability problem
title_sort randomized algorithm for solving the satisfiability problem
publishDate 1997
url http://sedici.unlp.edu.ar/handle/10915/24079
work_keys_str_mv AT cecchilaura arandomizedalgorithmforsolvingthesatisfiabilityproblem
AT cecchilaura randomizedalgorithmforsolvingthesatisfiabilityproblem
bdutipo_str Repositorios
_version_ 1764820466569052162

Ejemplares similares