International Business Machines Corporation
Transformation from general max sat to MAX 2SAT

Abstract:

A computer-implemented method for solving a MAX SAT instance in provided in which a MAX SAT instance is transformed into a MAX 3SAT instance. The MAX 3SAT instance is transformed into a MAX 2SAT instance which is solved for an optimum solution. A solution to the MAX SAT instance is recovered from the MAX 2SAT optimum solution.