Name
Title | ||
|---|---|---|
Counterexamples to the long-standing conjecture on the complexity of BDD binary operations |
Abstract | ||
|---|---|---|
In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input-output sizes. We present Boolean functions for which the time required by Bryant@?s algorithm is a quadratic of the input-output sizes for all nontrivial binary operations, such as @?, @?, and @?. For the operations @? and @?, we show an even stronger counterexample where the output BDD size is constant, but the computation time is still a quadratic of the input BDD size. In addition, we present experimental results to support our theoretical observations. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ipl.2012.05.007 | Inf. Process. Lett. |
Keywords | Field | DocType |
boolean function,output bdd size,binary decision diagram,nontrivial binary operation,computation time,e. bryant,linear time,input bdd size,long-standing conjecture,binary operation,input-output size,bdd binary operation,data structures,analysis of algorithms | Boolean function,Discrete mathematics,Combinatorics,Analysis of algorithms,Binary decision diagram,Quadratic equation,Counterexample,Time complexity,Conjecture,Mathematics,Binary operation | Journal |
Volume | Issue | ISSN |
112 | 16 | 0020-0190 |
Citations | PageRank | References |
8 | 0.52 | 2 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryo Yoshinaka | 1 | 172 | 26.19 |
| Jun Kawahara | 2 | 20 | 3.39 |
| Shuhei Denzumi | 3 | 13 | 3.01 |
| Hiroki Arimura | 4 | 1130 | 92.90 |
| Shin-ichi Minato | 5 | 725 | 84.72 |