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.