I am looking for references about the complexity of Boolean formula balancing problem. In particular,

  1. Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
  2. Is there a simple proof of Boolean formula balancing being in $\mathsf{AC^0}$?

By "simple" I mean a proof simpler than the one I mention below, in particular I am looking for a proof which doesn't depend on Boolean formula evaluation being in $\mathsf{NC^1}$.


Here all mentioned complexity classes are the uniform ones.

BFB (Boolean formula balancing):
Given a Boolean formula $\varphi$,
Find an equivalent balanced Boolean formula.

I am interested in the complexity of this problem, in particular simple proofs showing the problem is in $\mathsf{AC^0}$ (or even $\mathsf{TC^0}$ or $\mathsf{NC^1}$). The common balancing arguments like those based on Spira's lemma apply repeated structural modifications to the formula tree which seem to only give $BFB \in \mathsf{NC^2}$.

I have a proof for $BFB \in \mathsf{AC^0}$, however the proof is not simple and depends on the proof of $BFE \in \mathsf{NC^1}$.

BFE (Boolean formula evaluation)
Given a Boolean formula $\varphi$ and a truth assignment $\tau$ for variables in $\varphi$,
Does $\tau$ satisfy $\varphi$ ($\tau \vDash \varphi$)?

It is known from Sam Buss's celebrated result that Boolean formula evaluation ($BFE$) can be computed in $\mathsf{NC^1} = \mathsf{ALogTime}$ (see [Buss87] and [BCGR92]).

It follows (quite surprisingly, at least to me) that Boolean formulas balancing ($BFB$) is also in $\mathsf{NC^1}$:

The idea is that we can hardcode $\varphi$ in the input gates of $BFE$ to obtain a formula equivalent to $\varphi$ and this is a completely syntactic operation computable in $\mathsf{AC^0}$. Since $BFE$ has balanced formulas we obtain a equivalent balanced formula for $\varphi$. In other words, the algorithm is:

$$\ulcorner \varphi \urcorner \mapsto \ulcorner \lambda \vec{p}. Eval(\ulcorner \varphi \urcorner, \vec{p} )\urcorner$$


A simpler argument for $BFB$ being in $\mathsf{AC^0}$ (or $\mathsf{TC^0}$ or even $\mathsf{NC^1}$) would give a new simpler proof of $BFE \in \mathsf{NC^1}$ since it is easy to see that the balanced version of BFE can be solved in $\mathsf{NC^1}$ and we can compose it with $BFB$ and the result will be in $\mathsf{NC^1}$.


  1. Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$ ($BFB\in \mathsf{AC^1}$)?
  2. Is there a simpler argument (e.g. not relying on $BFE\in \mathsf{NC^1}$) for $BFB\in\mathsf{AC^0}$?
  • 4
    $\begingroup$ What definition of "balance" do you use? $\endgroup$ Dec 31, 2012 at 17:24
  • 1
    $\begingroup$ @Dana, we can use something like $Depth < 10\lg Size + 100 $ (i.e. $Depth = O(\lg Size)$ with specific constants). See also Bonnet and Buss's paper "Size-Depth Tradeoff for Boolean Formulae", 2002. $\endgroup$
    – Kaveh
    Jan 3, 2013 at 8:09
  • $\begingroup$ agreed the defn of "balancing" should be made clear. is this similar to the concept of balancing in binary trees? eg "self balanced trees" $\endgroup$
    – vzn
    Oct 23, 2013 at 20:57

2 Answers 2


I am not sure if this is very relevant but in Log-Space Algorithms for Paths and Matchings in k-Trees (building on a long history of past work and specifically on Arithmetizing classes around NC1 and L by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if the input tree is directly given in the string representation.

The basic idea is to represent the tree as a parenthesis expression and find balanced separators for these. Notice that we find leaf separators i.e. subtrees which are balanced w.r.t. number of leaves.


I stumbled upon this question now, many years later. In the interim the following paper has appeared:



There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '87, as was the original motivation of this question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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