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

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

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)$$.
• 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.