Probabilistic bounds and algorithms for the maximum satisfiability problem

In this paper we present a new method to analyze and solve the maximum satisfiability problem. We 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. Our algorithm generalizes the heuristic procedure given by Johnson, 1974.Research supported by AFOSR Grants 0271, 0066 and by NSF Grant 85-03212.