BDD’s and Factoring
Binary decision diagrams, pushdown machines, and factoring
Randy Bryant is famous for his work on BDD’s, which are one of the most powerful tools used today in the design and analysis of digital logic. While Randy has done other great work, his paper on BDD’s created an avalanche of research, papers, systems, and applications. This famous paper is one of the most cited in all of computer science. There are many additional papers that should probably cite him–after a while you stop getting citations, since the work is so well known. This phenomena is related to Ron Graham’s Award Lemma:
Lemma: For every field of science with awards, there is a , so that if you win at least awards, then you will win at least .
Today I plan to talk about BDD’s from the view of complexity theory, not from the view of a logic designer. I will explain what they are, why they are important, and the relation to problems near and dear to me–like factoring. Always factoring.
At the anniversary celebration of the creation of the School of Computer Science at Carnegie-Mellon (CMU) Randy, the Dean, made a comment that I think sums up his approach to many things. The , in 2006, was a big event and one of the greats of AI was speaking to a packed hall. John McCarthy was talking about the seminal work that was done at CMU, in the early years, especially highlighting the work of Allen Newell and Herbert Simon on list processing. Now there is no doubt that they were the first to create list processing languages, but it is unclear whether they actually invented the concept of a list. In any event, they shared, a well deserved, Turing award in 1975 for this and related work.
When John finished his talk to a huge applause, Randy, who was in the audience, stood up and started to question whether Newell and Simon actually invented the notion of a list. John was definitely taken aback: why would the Dean ask these questions about two of CMU’s greatest scientists? But, Randy is a true independent thinker, and he wanted to know–in front of hundreds of people–did Newell and Simon actually invent the list concept or not? The session chair quickly stepped in and the celebration moved on to another talk.
This was an especially interesting debate, since Newell was one of the wisest and kindest faculty that CMU probably has ever had; truly he is beloved by the entire CMU community. He taught me what little AI I know–in those days long ago–AI was called Complex Information Processing (CIP).
I still remember his great sense of humor, which helped make him such a wonderful teacher. The first day of his CIP class, our classroom was completely full, at least twenty students had to stand in the back of room. They had no seats, no desks. One of them raised a hand and asked Newell if we could possibly move to a larger room. He simply said, “in my experience, the room will grow in size as the class goes on.” Of course he was correct, after a few more class meetings, there were plenty of seats.
Randy never did get an answer to his question: who invented lists? I think raising the question shows his quest for knowledge, his ability to think out of the box, and his ability to not care what the answer is–as long as it is correct. I respect him very much for these traits.
So what is a BDD? It is a binary decision diagram. Simply, it is a way to represent a boolean function, that allows the discovery of properties of boolean functions that would otherwise be hard to determine.
Actually, Randy studied what are called Ordered Binary Decision Diagrams (OBDD), and today what I call BDD’s are a special case of OBDD–confused? I am doing this for two reasons. The special case that we will study has, up to a small factor, the same size as the more general OBDD’s. So if you are an expert, please do not get too upset at me; and if you are not, just be aware that I have simplified things to avoid complex notation. The essential ideas, the power of the method, are still the same.
Also by restricting ourselves to this special, but powerful class of BDD, we will be able to extend the notion of BDD’s in an interesting way. Since this extension is more interesting to theorists, than to logic designers, I believe that it is not yet well explored. But, I think it has great potential.
One of the great mysteries to me about BDD’s is that they are not–I believe–used much in the complexity theory arena, yet they are a simple generalization of something that we know well: finite state automata (fsa). One way to view a BDD is as a kind of fsa on “steroids.”
Suppose that where . In complexity theory we have many ways to define the complexity of . What BDD’s do is define the complexity of as this: Let be the size, in states, of the smallest deterministic finite state automata that accepts the language:
where is a permutation. Then, define as the minimum of over all permutations .
A classic example, that demonstrates the power of BDD’s, is the language of all strings of the form
where , for all indices . It is easy to see that a fsa for this language requires states: after scanning the first half of the string, the automata must “remember” different values. Any fewer states, forces the automata to confuse two strings, and therefore make a mistake.
Yet, there is something unsettling about this example. It only works, because the string is represented in a most inconvenient manner. Suppose instead the string is represented as:
Then, the fsa needs only states to accept the new language. This huge improvement is the fundamental idea of BDD’s:
Allow the inputs to be re-ordered in the most convenient way.
A Basic Property of BDD’s
One of the most important properties of a BDD is:
Theorem: Suppose that is at most and we know the permutation . Then, in polynomial time in , we can determine whether or not there is an so that . Even more, we can also count the number of , so that in the same time bound.
In many representations deciding if there is an so that is NP-hard. Here we can even count the exact number of such inputs.
The proof of this theorem depends on a simple property of deterministic finite state automata. Consider an fsa with states, that we wish to count the number of inputs of length that it accepts. We create a new fsa with at most states such that, (i) simulates on length inputs, and (ii) there are no cycles in ‘s finite state diagram. Then, we can label, inductively, the states of with the number of inputs that can reach that state. In this manner we can count the number of inputs that accepts.
The above argument is quite useful, and is only a slight extension of the well known fact that deciding if an fsa accepts some input is in polynomial time. Yet, this extension does not seem to be as well known as it should be.
Bounded Width Computations
There is a relation between read-once bounded width programs and BDD’s. Are they not the same? The answer is both yes and no.
A BDD can be viewed as a read-once bounded width computation, where the width is bounded by the number of states. So the answer is yes.
This is a bit misleading, however. The power of BDD’s is the ability to select the order of the inputs to the computation. The ability to vary the order of inputs to make the width of the computation smaller is what the theory of BDD representation is all about. So the answer is no.
Also in the next two sections, I will present two extensions to the basic BDD concept that will diverge greatly from bounded width computations.
There is a further reason that BDD are different from read-once computations. It is possible to generalize the BDD notion and replace finite state automata by a nondeterministic push down automata. Now the complexity of a boolean function is determined by the size, in states, of the smallest pushdown automata that accepts the language:
where is a permutation. Again we are free to chose the “best” permutation. Let us denote this minimum by .
The reason this is interesting is that the power of a pushdown trivially allows a kind of read-twice. Suppose the input is , then by placing it on the pushdown and popping it off at the end, such a machine can simulate the ability to see the string:
This is a special kind of read twice ability.
The counter-part of the basic theorem now is weaker:
Theorem: Suppose that is at most and we know the permutation . Then, in polynomial time in , we can determine whether or not there is an so that .
Note, we do not preserve the ability, to my knowledge, to be able to count the number of accepting paths.
The proof of this theorem is simple, but a bit curious. The proof is simply to note that to determine if for some , reduces to the emptiness problem for a pushdown machine. This can be done in polynomial time in the number of states of the machine.
However, the classic literature on language theory does not seem to prove this. The literature does prove that any such language is in polynomial time, but that is not exactly what we need. It is an issue of uniformity: we need given a pushdown machine in time polynomial in the size of , we can tell if is empty. That is different from the well known fact that is in polynomial time. Do you see the difference?
My guess is that most of the theorems about pushdown machines were proved long before the great interest in polynomial time. This is an aside, but clearly as our field advances we must re-examine old theorems and results–many may need to be re-proved in light of new concerns.
Another Extension of BDD’s
Define an encoding as a mapping so that (i) is computable in polynomial time and (ii) exists and is also computable in polynomial time. Obviously, this means that the mapping is an efficiently computable bijection on the set of length bit strings.
For many applications of the BDD concept to theory, we can allow much more powerful encodings than just permutations. Clearly, a permutation is an encoding in the sense that we mean here. But, many other natural mappings could be used:
- The encoding could be an arbitrary linear invertible map over .
- The encoding could be a permutation polynomial over the input;
- The encoding could be a piecewise linear map.
The latter could be a map that is defined, for example, as one bijection on the interval to itself, and another on to itself.
Of course, the more powerful the encoding allowed the more difficult it will be to prove lower bounds, or lower bounds may not even exist. Thus, it may be possible to change the complexity of a function dramatically.
Lower Bounds on BDD’s
One of the first theorems that Randy proved about BDD’s was a lower bound on . Let be the boolean function that is on strings of the form:
where as integers.
The importance of this function to Randy was that “real” digital logic had multipliers. Thus, he was quite interested in how large is the BDD representation. He proved the following pretty theorem:
Theorem: For large enough,
Randy used a lemma from an earlier paper of Bob Sedgewick and myself on related lower bounds via communication complexity. I have mentioned our work in an earlier post, and will return to it in the future. For the details of how Randy proved this theorem see his paper.
Philipp Woelfel, in 2005, improved this greatly to,
Theorem: For large enough,
These lower bounds do not apply to the extensions that we have raised: and other types of encodings.
The interest that I have in the previous lower bounds is their relationship to factoring. If has BDD complexity , then we can factor numbers of length in time polynomial in . The same is true, if we replace the BDD complexity by BDDPUSH complexity.
Suppose that for some ordering of there is an fsa that accepts if and only if . Then, there is an oracle that can answer any query of the form: Given are there so that ? Here is the concatenation of and . The existence of this oracle follows directly from the main theorem on BDD’s.
Then, by a standard self-reduction argument, we can factor. Suppose that we wish to factor . Then, we proceed to try and find the value of so that for some . We do this by guessing one bit of at a time, while restricting .
There are a number of interesting open problems. One is what is the value of ? If it is of the form , then what is the value of ? If it is small, then this could be a threat to factoring based cryptography.
Suppose we have a boolean function , how well can we approximate it with another boolean function so that ? For example, is the multiplication function is well approximated by such a boolean function?
Also what happens for non-standard encodings? Can we still prove exponential lower bounds on , or do these become too hard to prove? Of course, a better upper bound would be quite interesting.
The BDD measure of complexity is quite different from some of our standard measures. For example, some of our favorite boolean functions, old friends, that have high complexity in other measures are trivial in this model. For example, computing parity, or more generally any threshold function are easy in this model.
Finally, can BDD’s be used to solve, for example, the Junta problem? Or are there other possible applications?
This is the post.
To paraphrase Don Knuth: whenever you need more bits in a counter, it is a big deal. So thank you all for your kind support. On to the next power of two.