Branching programs provide lower bounds on the areas of multilective deterministic and nondeterministic VLSI-circuits |
| |
Authors: | Juraj Hromkovi Matthias Krause Christoph Meinel Stephen Waack |
| |
Affiliation: | Juraj Hromkovi
, Matthias Krause, Christoph Meinel,Stephen Waack |
| |
Abstract: | Each (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α),
, 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). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|