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


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.