# Can weight-restricted versions of monotone 2-SAT be decided in polynomial time?

I'm trying to answer a question from one of past test,

The question is to decide if the following language is $\mathrm{P}$ (can be decided in a polynomial time) or $\mathrm{NPC}$ (can be decided by non deterministic polynomial Turing machine and also complete).

• An instance of SAT is monotone if there are no negations $\neg x_j$ among any of the literals.
• The (Hamming) weight of a boolean string is just the number of "true" assignments; that is, for $x \in \{0,1\}^\ast$, the number of indices for which $x_j = 1$.

Then we define: $$\textrm{Special-}2\mathrm{SAT}=\Bigl\{ (\phi,k) \:\,\Big|\,\: \phi \text{ is monotone, and has a satisfying assignment with weight} \leqslant k \Bigr\}.$$

I thought that it's in $\mathrm{P}$ since I can go through all the literals and check that there are not negative forms, and then to choose $\binom{n}{x}$ for all $x=1,\ldots,k$ and for every choose check if these literals when given $1$ and the rest is $0$ and to check if it satisfiable, and it's still polynomial, isn't it?

The final answer was that it is $\mathrm{NPC}$ and there's a reduction from $\mathrm{VertexCover}$ to our problem.

What's wrong with what I described? I tried to make the suggested reduction, but I couldn't. Any help? Thanks.

• This would be a wonderful question for cs.stackexchange.com . Aug 8, 2012 at 11:27
• cs is a almost a dead place,sometimes there are no answer, and if so very late one , and there are a lot of people, specifically here, that are wonderful with this stuff. Aug 8, 2012 at 11:29
• I'm there frequently and questions seem to get answered reasonably promptly. Perhaps if more of the computational problems went there, it would see more activity. (You're not talking about 'cstheory', are you?) Aug 8, 2012 at 11:32
• Yes, for some reason people prefer post their cs questions here, and there's a reason.. Usually when I post there, I don't get answer for couple of hours,so I post here, get answered very nice and fast, and delete my question from csStackexchange.. Aug 8, 2012 at 11:34
• Computability Tag : "Questions about which problems are computable, or in general any question in recursion theory. Questions about the difficulty of solving particular problems should be tagged complexity." Aug 10, 2012 at 17:41

A polynomial-time algorithm runs in time $O(n^c)$ where $c$ is a constant independent of the input.
Your algorithm is not polynomial, since the exponent depends of the input. Assume that $k=n/2$, your method needs to check at least $n \choose n/2$ assignments which is exponential.
Specifically: for a 2-SAT instance $\phi$, we can construct a graph $G$, whose vertices are the literals $x_j$ and whose edges are the pairs $\{x_h, x_j\}$ which occur in some clause of $\phi$. Then a satisfying assignment to $\phi$ is the characteristic function of a vertex-set $C \subseteq V(G)$ which "covers" all of the edges (each edge is incident to some vertex in $C$); we call $C$ a vertex cover. The question of whether or not there is a satisfying assignment for $\phi$ which has weight at most $k$, is then equivalent to whether the graph $G$ has a vertex cover of most $k$ vertices.
• @Neil: Isn't a reduction from $2-SAT$ to $VC$? Aug 9, 2012 at 15:53