Boolean function with specific ОBDD representation

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.

Solved by user2517 (1,338 )
Feb 08, 2011 at 23:21