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

<ul>
<li>The hidden weighted bit function $HWB_n(x) = x_{sum}$ with $sum = x_1 + \ldots +x_n$ and $x_0 := 0$</li>
<li>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$.</li>
</ul>

<p>It is known that for these function the OBDD size is exponential (see e.g. <a href="http://books.google.de/books?id=-DZjVz9E4f8C&amp;lpg=PP1&amp;ots=WjOh0KA2Jv&amp;dq=wegener%20binary%20decision%20diagram&amp;pg=PP1#v=onepage&amp;q&amp;f=false">Branching Programs and Binary Decision Diagrams</a>). 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.</p>

CC BY-SA 2.5
2011-02-09T04:34:17.900Z
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.)
Noam
CC BY-SA 2.5
2011-02-08T23:21:33.240Z
2011-02-08T23:21:33.240Z
Marc Bury
<p>Fix $k=\log n$ and define the following function on $n$ bits: take the first $k^2$ bits and view them as $k$ numbers in the range $1..2^k$: $p_1 ... p_k$.  Now take the $p_1$'st bit, $p_2$'nd bit ... $p_k$'th bits of the input and view them as a $k$ bit number $p$.  The output is the value of the $p$'th bit of the input.</p>

<p>A palindromic OBDD of size $exp(k^2)$ can solve it by first reading and remembering  $p_1 ... p_k$, then reading these $k$ bits, on the first pass, and remembering $p$ and then reading the $p$'th bit on the 2nd pass.</p>

<p>Look at a single pass OBDD and let us restrict the function by dictating that $p_1 ... p_k$ will be equal to the last $k$ indices of the input, and thus $p$ is specified by the last $k$ bits of the input.  It is easy to see that $\Omega(n)$ bits need to be remembered about the first $n-k^2-k$ non-restricted bits of the input in order for the value of the $p$'th bit to be recovered (this is the Index function in communication complexity -- see example 4.18 in <a href="http://books.google.com/books?id=9A_9Jcs1ZJQC&amp;printsec=frontcover&amp;dq=kushilevitz+nisan&amp;source=bl&amp;ots=XmYaji8mG2&amp;sig=wa2l1nog3LsW5-Y73mYe-sDxYEM&amp;hl=en&amp;ei=e6NRTd70Jo6z8QOq_62jCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=3&amp;ved=0CCgQ6AEwAg#v=onepage&amp;q&amp;f=false" rel="nofollow">Communication Complexity book</a>, page 49).</p>

<p>This gives a gap $n^{\log n}$ vs. $exp(n)$ -- to get poly vs non-poly just use $N=n^{\log n}$ bits and ignore all but the first $n$.</p>

CC BY-SA 2.5
2011-02-09T15:24:46.567Z
Thank you Noam. I am missing the logic, if the palindrome BDD is $exp(n)$ wouldn't it be bigger that the 1-OBDD? (taking logs)?
Leon Leon
CC BY-SA 2.5
2011-02-09T19:01:14.413Z
exp(n) is on a 1-OBDD ("remember n bits" = size is exp(n)), and n^logn is on a 2-pass-OBDD ("remember k^2 bits" = size 2^{k^2}=n^logn)
Noam
CC BY-SA 2.5
2011-02-08T20:16:50.840Z
2011-02-08T23:11:50.063Z
2011-02-08T23:11:50.063Z
Noam
<p>I am looking for a class of boolean functions on $n$ variables with the following property:</p>

<ol>
<li>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$</li>
<li>Read once polynomial size OBDD doesn't exist for the boolean function.</li>
</ol>

<p>I did some experiments with the CUDD package to no success.</p>

<p>Any ideas how to find an instance of such function?</p>

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

<cc.complexity-theory><boolean-functions><binary-decision-diagrams>
Boolean function with specific ОBDD representation
Leon Leon
# Boolean function with specific ОBDD representation

(Asked by: username_0 on 2011-02-08)

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

**Tags:** cc.complexity-theory, boolean-functions, binary-decision-diagrams

---

## 2 answers

### Answer by username_1 on 2011-02-08. Score: 5 | Accepted answer

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](http://books.google.de/books?id=-DZjVz9E4f8C&lpg=PP1&ots=WjOh0KA2Jv&dq=wegener%20binary%20decision%20diagram&pg=PP1#v=onepage&q&f=false)). 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:**
> **username_2**: 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.)  

---

### Answer by username_2 on 2011-02-08. Score: 5

Fix $k=\log n$ and define the following function on $n$ bits: take the first $k^2$ bits and view them as $k$ numbers in the range $1..2^k$: $p\_1 ... p\_k$. Now take the $p\_1$'st bit, $p\_2$'nd bit ... $p\_k$'th bits of the input and view them as a $k$ bit number $p$. The output is the value of the $p$'th bit of the input.

A palindromic OBDD of size $exp(k^2)$ can solve it by first reading and remembering $p\_1 ... p\_k$, then reading these $k$ bits, on the first pass, and remembering $p$ and then reading the $p$'th bit on the 2nd pass.

Look at a single pass OBDD and let us restrict the function by dictating that $p\_1 ... p\_k$ will be equal to the last $k$ indices of the input, and thus $p$ is specified by the last $k$ bits of the input. It is easy to see that $\Omega(n)$ bits need to be remembered about the first $n-k^2-k$ non-restricted bits of the input in order for the value of the $p$'th bit to be recovered (this is the Index function in communication complexity -- see example 4.18 in [Communication Complexity book](http://books.google.com/books?id=9A_9Jcs1ZJQC&printsec=frontcover&dq=kushilevitz+nisan&source=bl&ots=XmYaji8mG2&sig=wa2l1nog3LsW5-Y73mYe-sDxYEM&hl=en&ei=e6NRTd70Jo6z8QOq_62jCw&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCgQ6AEwAg#v=onepage&q&f=false), page 49).

This gives a gap $n^{\log n}$ vs. $exp(n)$ -- to get poly vs non-poly just use $N=n^{\log n}$ bits and ignore all but the first $n$.

> **Comments:**
> **username_0**: Thank you Noam. I am missing the logic, if the palindrome BDD is $exp(n)$ wouldn't it be bigger that the 1-OBDD? (taking logs)?  
> **username_2**: exp(n) is on a 1-OBDD ("remember n bits" = size is exp(n)), and n^logn is on a 2-pass-OBDD ("remember k^2 bits" = size 2^{k^2}=n^logn)  

---

