7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – Noam
    Feb 9 '11 at 4:34
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Leon Leon
    Feb 9 '11 at 15:24
  • $\begingroup$ 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) $\endgroup$
    – Noam
    Feb 9 '11 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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