GD-SAT model and crossover line

Abstract

In the last decade a lot of effort has been invested into both theoretical and experimental analysis of SAT phase transition. However, a deep theoretical understanding of this phenomenon is still lacking. It is still a very challenging problem to determine a relationship between crossover points for different SAT problems. This paper introduces one new class of randomly generated SAT problems, GD-SAT, and we experimentally show there is a phase transition for the problems in this class. On the basis of both analytical and experimental arguments we conjecture that there is a surprisingly simple, linear relationship between crossover points for problems in this class. This relationship is of both theoretical and practical importance.