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

Question

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.

Answer 1

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.

Answer 2

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.