Probabilistic bounds and algorithms for the maximum satisfiability problem

In this paper the authors present a new method to analyze and solve the maximum satisfiability problem. They randomize the Boolean variables, assign probabilities to their possible values and, by using recently developed probabilistic bounds of the authors, present a deterministic procedure to obtain solution to the maximum satisfiability problem. The present algorithm generalizes the heuristic procedure given by Johnson.