Parameterized Complexity of MaxSat Above Average

Details Parameterized Complexity of MaxSat Above Average Parameterized Complexity of MaxSat Above Average

2011-08-23

arxiv.org/abs/1108.4501v2

Computer Science

Computational Complexity

Scientific paper

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 $r_1,..., r_m$ be the number of literals in the clauses of $F$. Then $asat(F)=\sum_{i=1}^m (1-2^{-r_i})$ 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 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 MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (arXiv:1104.1135v3). In fact, we consider a more refined version of {\sc MaxSat-AA}, {\sc Max-$r(n)$-Sat-AA}, where $r_j\le r(n)$ for each $j$. Alon {\em et al.} (SODA 2010) proved that if $r=r(n)$ is a constant, then {\sc Max-$r$-Sat-AA} is fixed-parameter tractable. We prove that {\sc Max-$r(n)$-Sat-AA} is para-NP-complete for $r(n)=\lceil \log n\rceil.$ We also prove that assuming the exponential time hypothesis, {\sc Max-$r(n)$-Sat-AA} is not in XP already for any $r(n)\ge \log \log n +\phi(n)$, where $\phi(n)$ is any unbounded strictly increasing function. This lower bound on $r(n)$ cannot be decreased much further as we prove that {\sc Max-$r(n)$-Sat-AA} is (i) in XP for any $r(n)\le \log \log n - \log \log \log n$ and (ii) fixed-parameter tractable for any $r(n)\le \log \log n - \log \log \log n - \phi(n)$, where $\phi(n)$ is any unbounded strictly increasing function. The proof uses some results on {\sc MaxLin2-AA}.

Affiliated with

Also associated with

No associations

Rating

Parameterized Complexity of MaxSat Above Average does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parameterized Complexity of MaxSat Above Average, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Complexity of MaxSat Above Average will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66840