SAT-problems: new findings
Christian Posthoff, Bernd Steinbach · 2007
Abstract:- SAT-problems in general and 3-SAT problems in particular are very important and interesting NP-complete problems with many applications in different areas. In several previous papers, before all in [2] and in [5], we showed the use of ternary vectors and set-theoretic considerations as well as binary codings and bit-parallel vector operations in order to solve this problem. The approach does not use any of the classical search methods, it uses more constructive ways to build possible solutions on the basis of partial solutions which are more or less easy to find. Experiments showed that this approach is very competitive and efficient. After the parallelism of the solution process has been established on the register level, i.e. related to the existing hardware, it could also be shown that it is very promising and efficient to extend the ideas and concepts to the use of several processors working in parallel (see, for instance, [8]). This paper now presents some refinements of the existing approaches with an overwhelming and very surprising increase of the efficiency of the algorithms and implementations. The presentation relates to one processor, the transfer to a multi-processor system will be presented as soon as possible.