Consider instances of SATISFIABILITY in which each clause has one of the forms {x}, { ¯x}, or { ¯x, y}, where x and y are variables. Given such an instance and a nonnegative weight for each clause,...

Consider instances of SATISFIABILITY in which each clause has one of the

forms {x}, { ¯x}, or { ¯x, y}, where x and y are variables. Given such an instance

and a nonnegative weight for each clause, find (in polynomial time) a truth

assignment that maximizes the total weight of the satisfied clauses.

Hint: Reduce this to the MINIMUM CAPACITY CUT PROBLEM.