Do you know the complexity of the following decision problem?

Given a quantified boolean formula (QBF) $\phi$ with $2n$ free variables with $n\in\mathbb{N}$. Is there a satisfying assignment s.t. exactly $n$ free variables are true and $n$ free variables are false.

I am also interested in the easier case, where we consider propositional logic instead of QBF. What would the complexity be then?

  • 3
    $\begingroup$ It is straight forward how to turn an arbitrary formula $\varphi$ with $n$ variables to a formula $\psi$ with $2n$ variables s.t. $\varphi$ is satisfiable iff there is a satisfying assignment with hamming weight $n$ for $\psi$. The reverse direction is also not difficult. $\endgroup$ – Kaveh Sep 22 '15 at 18:47
  • $\begingroup$ Sorry, the first direction by intuition seems possible and I think I know how. The second direction does not seem obvious at all. Can you give pointers? $\endgroup$ – Heinrich Ody Sep 23 '15 at 9:34

Browse other questions tagged or ask your own question.