Lower and Upper Bounds for Random Mimimum Satisfiability Problem

Given a Boolean formula in conjunctive normal form with n variables and m = rn clauses, if there exists a truth assignment satisfying (1 - 2(-k) - q(1 - 2(-k))) m clauses, call the formula q-satisfiable. The Minimum Satisfiability Problem (MinSAT) is a special case of q-satisfiable, which asks for an assignment to minimize the number of satisfied clauses. When each clause contains k literals, it is called MinkSAT. If each clause is independently and randomly selected from all possible clauses over the n variables, it is called random MinSAT. In this paper, we give upper and lower bounds of r (the ratio of clauses to variables) for random k-CNF formula with q-satisfiable. The upper bound is proved by the first moment argument, while the proof of lower bound is the second moment with weighted scheme. Interestingly, our experimental results about MinSAT demonstrate that the lower and upper bounds are very tight. Moreover, these results give a partial explanation for the excellent performance of MinSatz, the state-of-the-art MinSAT solver, from the perspective of pruning effects. Finally, we give a conjecture about the relationship between the minimum number and the maximum number of satisfied clauses on random SAT instances.