Parameterized Complexity of MaxSat Above Average

Abstract

In MaxSat, we are given a CNF formula F with n variables and m clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let P r1, . . . , rm be the number of literals in the clauses of F. Then asat(F) = m i=1(1 − 2 −ri ) is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least asat(F) clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least asat(F) + k clauses, where k is the (nonnegative) parameter. We prove that MaxSat-AA is para-NP-complete and thus, MaxSat-AA is not fixed-parameter tractable unless P=NP. This is in sharp contrast to the similar problem MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (FSTTCS 2011).