ALGORITMO NUMÉRICO EN PARALELO PARA EL PROBLEMA DE SATISFACCIÓN LÓGICA Y PROBLEMAS NP
Se presenta una nueva versión modificada de un algoritmo numérico y paralelo para resolver el problema de satisfacción lógica con cláusulas en forma conjuntiva normalizada. La forma de resolver el problema no usa algebra, ni estrategias de búsqueda computacionales como ramificación limitada, búsqueda adelante y atrás, representación por árboles, etc. El algoritmo se basa en la clase especial de problemas de satisfacción lógica: problema simple de satisfacción lógica. El diseño del principal algoritmo incluye ejecución paralela, orientación a objetos y terminación abrupta, como en la versión anterior, pero en esta versión se incluye guardar información de los casos fallidos resultantes de la ejecución en paralelo para mejorar la eficiencia y favorecer la terminación abrupta. El resultado es un algoritmo lineal con respecto al número de cláusulas más un proceso de datos sobre las soluciones parciales de subproblemas simples de satisfacción lógica y con límite iteraciones, donde
es el número de variables lógicas. La novedad de la solución es un algoritmo lineal, cuya complejidad es menor o igual que la complejidad de los algoritmos del estado del arte. La relación con la clase NP es presentada al final.
ALGORITMO NUMÉRICO EN PARALELO PARA EL PROBLEMA DE SATISFACCIÓN LÓGICA Y PROBLEMAS NP
-
DOI: 10.22533/at.ed.3172262222117
-
Palavras-chave: Teoría de la Computación, Lógica, SAT, K-SAT, Complejidad de Algoritmos, Clase NP.
-
Keywords: Computer Theory, Logic, SAT, K-SAT, Complexity of Algorithms, Class NP.
-
Abstract:
A novel modified numerical parallel algorithm for solving the classical Decision Boolean Satisfiability problem with clauses in conjunctive normal form is depicted. The approach for solving SAT is without using algebra or other computational search strategies such as branch and bound, back-forward, tree representation, etc. The method is based on the special class of problems, Simple Decision Boolean Satisfiability problem. The design of the main algorithm includes parallel execution, object oriented, and short termination as the previous versions but it keeps track of the parallel tested unsatisfactory binary values to improve the efficiency and to favor short termination. The resulting algorithm is linear with respect to the number of clauses plus a process data on the partial solutions of the Simple Decision Boolean Satisfiability problems and it is bounded by 2ⁿ iterations where n is the number of logical variables. The novelty for the solution is a linear algorithm, such its complexity is less or equal than the algorithms of the state of the art. The relation with the class NP is depicted at the end.
- CARLOS BARRON ROMERO
