PROBABILISTIC ESTIMATES FOR THE GENERALIZED MAXIMUM SATISFIABILITY PROBLEM

The generalized maximum satisfiability problem (GMAXSAT) deals with va riables taking their values in a finite set. A set of logical clauses is given and the goal is to find an assignment of values to the variab les, minimizing the number beta of unsatisfied clauses. For randomly g enerated instances of alpha uniform type we study the distribution of beta, as well as the distribution of the maximal size alpha of a satis fiable subproblem, by means of the first and second moment method (Spe ncer, 1987). Numerical estimates for the distribution of alpha and bet a are given for some instances. In relation with the asymptotic behavi or, we show that alpha has almost surely three possible values only. F urthermore, in the spirit of Burkard and Fincke (1985), we show that f or some sequences of random instances, the size of which tends to infi nity, the relative error of any algorithm for GMAXSAT tends almost sur ely towards zero.