کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427684 | 686541 | 2012 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Counterexamples to the long-standing conjecture on the complexity of BDD binary operations Counterexamples to the long-standing conjecture on the complexity of BDD binary operations](/preview/png/427684.png)
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.
► We disprove the long-standing conjecture on the complexity of BDD binary operations.
► We present functions for which Bryantʼs algorithm takes input–output quadratic time.
► Including examples whose output is constant while the running time is quadratic.
► Experimental results by existing implementations clearly support our discussion.
Journal: Information Processing Letters - Volume 112, Issue 16, 31 August 2012, Pages 636–640