scientific article; zbMATH DE number 3866582

From MaRDI portal
Publication:3334079





[For the entire collection see Zbl 0538.00024.] It is known that depth and capacity of branching programs are lower bounds on time resp. space for any reasonable model of computation. The capacity of a branching program is the logarithm of its size. In order to prove time-space trade-offs one considers depth restricted branching programs like one-time-only branching programs, branching programs with minimal depth and real-time branching programs. It is shown that all these models coincide for symmetric Boolean functions. Efficient algorithms are given for the construction of optimal one-time-only branching programs and optimal decision trees for symmetric Boolean functions. The running time of these algorithms is of the same size as the constructed program. Finally the most difficult symmetric functions are described.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3334079)