<p>Do you know the complexity of the following decision problem?</p>

<p>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 <code>true</code> and $n$ free variables are <code>false</code>. </p>

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

CC BY-SA 3.0
2015-09-22T18:47:15.987Z
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.
Kaveh
CC BY-SA 3.0
2015-09-23T09:34:03.573Z
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?
Heinrich Ody
<time-complexity><sat>
Complexity of QBF with Restrictions on Models
Heinrich Ody
# Complexity of QBF with Restrictions on Models

(Asked by: username_0 on 2015-09-22)

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?

**Tags:** time-complexity, sat
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  

---

## 0 answers

