# 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 . – Niel de Beaudrap Aug 8 '12 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. – Jozef Aug 8 '12 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?) – Niel de Beaudrap Aug 8 '12 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.. – Jozef Aug 8 '12 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." – William Aug 10 '12 at 17:41

## 2 Answers

To answer the second part of your question, with respect to NP-completeness:

A satisfying assignment to a monotone instance of 2-SAT is some setting of the literals, where at least one of the two boolean variables in each clause must be set to "1". This property is analogous, in a graph, of each edge having one of its two vertices included in a set of "marked" elements.

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$? – Jozef Aug 9 '12 at 15:53
• @Jozef: Note that the monotonicity of the formula is crucial, as well as the fact that the decision problem of whether there is a satisfying assignment with a weight at most some input figure. (Note that absolutely every monotonic SAT forumla is satisfiable; it's just a question of what kinds of satisfiable solutions it has, and the weight restriction corresponds exactly to the size of the vertex cover.) – Niel de Beaudrap Aug 9 '12 at 16:00

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.