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

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

- 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$
- 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.

External links referenced by this document: