# Reduction from SAT to SAT with exactly k true variables

Let $$L$$ be defined as follows:

$$\small L = \{(\phi, k) \mid \phi \in SAT \mbox{ and there is a satisfying assignment for \phi having exactly k true variables} \}$$

I am struggling to show that $$SAT\leq_{p} L$$, I can't figure what $$k$$ should be and how to reconstruct $$\phi$$.

Let $$\phi'$$ be a SAT formula with $$n$$ variables.
Consider the pair $$(\phi, k)$$ where
• $$\phi$$ is a formula with $$2n$$ variables that is obtained from $$\phi'$$ by adding $$n$$ new variables $$x_1, \dots, x_n$$ (if you want each new variable $$x_i$$ to appear in at least one clause you can add the trivial clause $$(x_i \vee \overline{x}_i)$$).
• $$k=n$$.
If $$\phi$$ is satisfiable then any satisfying truth assignment for $$\phi$$ restricted to the variables in $$\phi'$$ is also a satisfying truth assignment for $$\phi'$$.
If $$\phi'$$ is satifiable, consider any satisfying truth assignment $$\tau'$$ and let $$n'$$ be the number of true variables in $$\tau'$$. You can obtain a satisfying truth assignment for $$\phi$$ by setting all variables of $$\phi'$$ according to $$\tau'$$ and any choice of exactly $$n-n'$$ variables from $$x_1, \dots, x_n$$ to true. Notice that this is always possible since $$0 \le n-n' \le n$$.