We 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 pair)
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.
(This is a modified version of C-216.)