IMAGE PROCESSING, PATTERN RECOGNITION

Recognition of zero bits of 3-sat problem by applying linear algebra’s methods

Yu. Yu. Ogorodnikov, R. T. Faizullin

Omsk State Technical University

Abstract: The paper presents two heuristic methods of recognizing zero bits satisfiability problem. The first is based on the reduction of the satisfiability problem to an equivalent problem of minimizing a continuous smooth function by method of successive approximations, extended by changing the order of calculation of variables. Another way is to reduce to a system of linear algebraic equations with symmetric diagonally dominant matrix.

Keywords: satisfiability, method of successive approximations, the order of calculation of variables, diagonal methods, factorization.

Received: 03.02.2014