NP-Completeness of SAT with given hamming weight k [duplicate]

Question

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction.

Input: A propositional formula $\varphi$ and a number $k$.

Output: Yes if exists an valuation $\sigma$ that satisfies the formula $\varphi$ and the hamming weight of $\sigma$ is $k$ ( Exactly k propositional variables have the value 1 on the assigment $\sigma$). Otherwise, output is NO

Answer 1

There is a simple reduction from the Clique problem, i.e. given some (undirected, simple) graph $G = (V, E)$ and some number $k$ we are asked whether or not $G$ contains a clique of size at least $k$.

Now, introduce variables $x_v$ for every vertex $v \in V$ and consider the formula $$\psi(G) = \bigwedge_{v \in V} \bigwedge_{w \in V} (x_v \wedge x_w \to [Evw]) $$ where $[Evw]$ is replaced by $1$ if $vw \in E$ and $0$ otherwise. Then some set $X \subseteq V$ is a clique if and only if setting precisely those variables corresponding to the vertices in $X$ to $1$ (and all others to $0$) yields a satisfying assignment for $\psi(G)$.

Let us prove this rigorously:

• Suppose that $X$ is a clique. Then for any distinct $v, w \in X$ the graph $G$ contains the edge $vw$, and hence $x_v \wedge x_w \to [Evw]$ evalutes to $1$. Also note that if at least one of $v$ and $w$ is not in $X$, then $x_v \wedge x_w \to [Evw]$ is trivially satisfied as the premise of the implication does not hold. Hence setting exactly the variables corresponding to the vertices in $X$ to $1$ satisfies $\psi(G)$.
• Suppose that $X$ is not a clique. Then there must exist distinct $v, w \in X$ such that $vw$ is not an edge in $G$ and hence, $x_v \wedge x_w \to [Evw]$ evaluates to $0$, yielding that setting precisely the variables corresponding to the vertices in $X$ to $1$ does not satisfy $\psi(G)$.

This immediately gives us the desired reduction by mapping Clique-instances $(G, k)$ to $(\psi(G), k)$. Clearly, computing $\psi(G)$ from $G$ can be done in polynomial time, and $\psi(G)$ has a satisfying assignment of weight $k$ if and only if $G$ has a clique of size $k$.

We conclude that your problem is $\mathsf{NP}$-complete.