On Dynamic Phase Transitions in Satisfiability Problems
John Ardelius · 2005
The problems to optimize properties of a frustrated system of many variables is a complex matter. Such problems arise in both combinatorial computational problems as well as in complex materials such as spin glasses. Since the theoretical treatment of such system is very hard and complicated one would like to find simpler methods to examine them. In this thesis random K-SAT problems are studied. We have developed a new heuristic method called ASAT which is a stochastic local search method which seem to be faster and simpler than existing ones. It is able to solve problem instances in linear time up to the constraint per variable ratio 4.21. We also examine the state space structure seen by the heuristic by a procedure called ’Simulated heating’. This also reveals the optimal value for the noise parameter in the optimization problem. How this scale with constraint size, K, is also investigated. Finally we use a statistic approach and model random 3-SAT problems with master equations.