Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits
- Hromkovič, Juraj
- Krause, Matthias
- Meinel, Christoph
- Waack, Stephen
DOIAbstract
AbstractEach (nondeterministic) multilective VLSI-circuit C of area A can be simulated by an oblivious (disjunctive) branching program of width exp(O(A)) which has the same multiplicity of reading as C. That is why exponential lower bounds on the width of (disjunctive) oblivious branching programs of linear depth provide lower bounds of order Ω(n1–2α), 0≤α<12, on the area of (nondeterministic) multilective VLSI-circuits computing explicitly defined one-output Boolean functions, if the multiplicity of reading is bounded by O(logαn). Lower bounds are derived for the sequence equality problem (SEQ) and the graph accessibility problem (GAP)
Add to ORKG