Average-case analysis for the MAX-2SAT problem

AbstractWe propose a simple probability model for MAX-2SAT instances for discussing the average-case complexity of the MAX-2SAT problem. Our model is a “planted solution model”, where each instance is generated randomly from a target solution. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pairs) is the optimal solution for the generated instance with high probability. We then give a simple linear-time algorithm based on a message passing method, and we prove that it solves the MAX-2SAT problem with high probability for random MAX-2SAT instances under this planted solution model for probability parameters within a certain range