A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming

We study the probabilistic behaviour of solutions of random instances of the Boolean Satisfiability (SAT) and Constraint Satisfaction Problems (CSPs) that generalize the standard notion of a satisfying assignment. Our analysis focuses on a special type of generalized solutions, the (1,0)-super solutions. For random instances of k-SAT, we establish the exact threshold of the phase transition of the solution probability for k≤3, and give upper and lower bounds on the threshold of the phase transition for the case of k≥4. For CSPs, we derive an upper bound on the threshold of having a (1,0)-super solution asymptotically with probability 1, and establish a condition for the expected number of super solutions to grow exponentially.