<p>The main difference between time and space is that you can reuse space that is not needed anymore.</p>

<p>If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$.  Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives you a linear space requirement.</p>

<p>This fact is explained quite well in standard introductory text books on Complexity Theory.  You can have a look into Sipser's <em>Introduction to the Theory of Computation</em>, for example. On page 332 (3rd edition) he explains the space requirement for SAT, of which QBF is a generalization.</p>

CC BY-SA 3.0
2015-09-05T15:47:57.353Z
Thanks for your comment. I don't remember Sipser mentioning the QBF problem in that book, but I'll have another look. I understand you can reuse the space, but you still spawn more and more new "formulas". Note that I am not adding the space needed at each stage of the calculation.
Nicolas Mattia
CC BY-SA 3.0
2015-09-05T15:50:23.313Z
My bad. Page 332 of 3rd edition. The example is actually for SAT. Thank you very much!
Nicolas Mattia
CC BY-SA 3.0
2015-09-05T14:44:27.543Z
2015-09-06T04:55:38.107Z
2015-09-06T04:55:38.107Z
Daniel Borchmann
<p>I came across <a href="https://en.wikipedia.org/wiki/True_quantified_Boolean_formula#Solving" rel="nofollow">this</a> section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any reference.</p>

<p>For a given QBF
$$Q_1x_1Q_2x_2...Q_nx_n\phi(x_1,x_2,...,x_n)$$ </p>

<p>for each quantifier, the algorithm presented evaluates </p>

<p>$$ A = Q_2x_2...Q_nx_n\phi(0,x_2,...,x_n)$$ 
$$B = Q_2x_2...Q_nx_n\phi(1,x_2,...,x_n)$$ </p>

<p>and returns $A\wedge B$ for $Q_1 = \forall$ and $A\lor B$ for $Q_1 = \exists$. The way I work it out the space should be $O(2^n)$ instead of $O(n + \log(n)) = O(n)$. When I solve a QBF on paper, I realize it is not exponential, so something must be terribly wrong with my analysis.</p>

<p>At each step, the new $A$ and $B$ have one quantifier less, but there are twice as many expressions. I assumed that would build up as
$$ 1: n$$
$$ 2 : (n-1) + (n-1) $$
$$ 3 : (n-2) + (n-2) + (n-2) + (n-2) $$
$$ \ldots $$
$$ k : 2^k (n-k) $$</p>

<p>which goes all the way up to $2^{n-1}$ before decreasing to zero. Can anyone provide a pointer on what I am doing wrong, or even better a good reference?</p>

<p>Thanks</p>

CC BY-SA 3.0
2015-09-06T04:16:34.947Z
Please check our [tour] and [help/on-topic]. This question seems more suitable for [cs.se].
Kaveh
<sat><space-complexity><pspace>
Space requirements for solving True Quantified Boolean Formulas problem
Nicolas Mattia
# Space requirements for solving True Quantified Boolean Formulas problem

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

I came across [this](https://en.wikipedia.org/wiki/True_quantified_Boolean_formula#Solving) section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any reference.

For a given QBF
$$Q\_1x\_1Q\_2x\_2...Q\_nx\_n\phi(x\_1,x\_2,...,x\_n)$$

for each quantifier, the algorithm presented evaluates

$$ A = Q\_2x\_2...Q\_nx\_n\phi(0,x\_2,...,x\_n)$$
$$B = Q\_2x\_2...Q\_nx\_n\phi(1,x\_2,...,x\_n)$$

and returns $A\wedge B$ for $Q\_1 = \forall$ and $A\lor B$ for $Q\_1 = \exists$. The way I work it out the space should be $O(2^n)$ instead of $O(n + \log(n)) = O(n)$. When I solve a QBF on paper, I realize it is not exponential, so something must be terribly wrong with my analysis.

At each step, the new $A$ and $B$ have one quantifier less, but there are twice as many expressions. I assumed that would build up as
$$ 1: n$$
$$ 2 : (n-1) + (n-1) $$
$$ 3 : (n-2) + (n-2) + (n-2) + (n-2) $$
$$ \ldots $$
$$ k : 2^k (n-k) $$

which goes all the way up to $2^{n-1}$ before decreasing to zero. Can anyone provide a pointer on what I am doing wrong, or even better a good reference?

Thanks

**Tags:** sat, space-complexity, pspace
> **Comments:**
> **username_1**: Please check our [tour] and [help/on-topic]. This question seems more suitable for [cs.se].  

---

## 1 answers

### Answer by username_2 on 2015-09-05. Score: 4 | Accepted answer

The main difference between time and space is that you can reuse space that is not needed anymore.

If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$. Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives you a linear space requirement.

This fact is explained quite well in standard introductory text books on Complexity Theory. You can have a look into Sipser's *Introduction to the Theory of Computation*, for example. On page 332 (3rd edition) he explains the space requirement for SAT, of which QBF is a generalization.

> **Comments:**
> **username_0**: Thanks for your comment. I don't remember Sipser mentioning the QBF problem in that book, but I'll have another look. I understand you can reuse the space, but you still spawn more and more new "formulas". Note that I am not adding the space needed at each stage of the calculation.  
> **username_0**: My bad. Page 332 of 3rd edition. The example is actually for SAT. Thank you very much!  

---

