On threshold properties of k-SAT: An additive viewpoint

The SAT problem is one of the basic problems from complexity theory. When SAT is restricted to clauses of length k, we obtain the so-called k-SAT problem. For k ≥ 3, it is a N P-complete problem but it is believed that most of the instances are easy to solve. In fact, numerical evidence shows that a threshold phenomenon is to be expected. Up to now only upper bounds and lower bounds of the prospective value of the transition point have been obtained. Concerning lower bounds, they are obtained by considering special algorithms for which we can prove that it solves almost all instances of k-SAT if the ratio of the number of clauses by the number of variables is less than some given value. In this expository paper, we propose a completely new approach on the problem of evaluating from below the prospective value of the transition point by showing a connection between k-SAT and number theory. More precisely, it is based on additive number theoretic considerations and avoids the use of any specific algorithm by directly counting the number of solutions to a system encoding an instance of k-SAT.