Theoretical Computer Science
cc.complexity-theory boolean-functions binary-decision-diagrams
Updated Thu, 23 Jun 2022 17:52:11 GMT

Boolean function with specific ОBDD representation

I am looking for a class of boolean functions on $n$ variables with the following property:

  1. When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD is polynomial in $n$
  2. Read once polynomial size OBDD doesn't exist for the boolean function.

I did some experiments with the CUDD package to no success.

Any ideas how to find an instance of such function?

(There is a chance such functions don't exist but I would not bet much money on this).


I think all pointer functions are hard for OBDDs and easy for a 2-OBDD. Example for such pointer functions are

  • The hidden weighted bit function $HWB_n(x) = x_{sum}$ with $sum = x_1 + \ldots +x_n$ and $x_0 := 0$
  • The indirect storage access (similar to the function in Noam's answer) $ISA_n$ with $n = 2^k$. Input is $(x,y)$ with $x \in \lbrace 0,1 \rbrace^n$ and $k \in \lbrace 0,1 \rbrace^k$. Let $\vert y \vert$ the integer represented by the binary number $y$. Then the input $y$ gives a part $x_{\vert y \vert},\ldots,x_{\vert y \vert +k-1}$ of the input $x$ (indices are taken mod $n$). Let $a$ be the integer represented by this part. The output of $ISA_n(x,y)$ is $x_a$.

It is known that for these function the OBDD size is exponential (see e.g. Branching Programs and Binary Decision Diagrams). But there is a polynomial 2-OBDD for these functions by parsing the address in the first phase and reading the relevant data in the second.

Comments (1)

  • +0 – This is indeed the right way to look at this. (My version was just designed so that the lower bound is especially easy to prove from scratch.) — Feb 09, 2011 at 04:34