Is Max 3-SAT a W hard problem, parmeterized by some parmeterize? I can't find the relevant literature.
I accept any parameterization.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The W hierarchy consists of classes of decision problems. The decision versions of MAX-SAT problems are just slightly disguised SAT problems. For example, to transform the decision problem "is there a variable assignment that satisfies k clauses?", add a unique variable to each CNF clause, then add a constraint that demands that at least k of the unique variables be set false. (All this can be done in polynomial time.) If the resulting SAT instance is satisfiable, the answer to the MAX-SAT problem is yes, otherwise the answer is no.