zbMATH — the first resource for mathematics

Time-space trade-offs for branching programs. (English) Zbl 0593.68038
Summary: Branching program depth and the logarithm for branching program complexity are lower bounds on time and space requirements for any reasonable model of sequential computation. In order to gain more insight to the complexity of branching programs and to the problems of time-space trade-offs one considers, on one hand, width-restricted and, on the other hand, depth-restricted branching programs. We present these computation models and the trade-off results already proved. We prove a new result of this type by presenting an effectively defined Boolean function whose complexity in depth-restricted one-time-only branching programs is exponential while its complexity even in width-2 branching programs is polynomial.

68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Bollobás, B., Extremal graph theory, (1978), Academic Press New York · Zbl 0419.05031
[2] Borodin, A.; Dolev, D.; Fich, F.E.; Paul, W., Bounds for width two branching programs, (), 87-93
[3] Chandra, A.K.; Furst, M.L.; Lipton, R.J., Multiparty protocols, (), 94-99
[4] Cobham, A., The recognition problem for the set of perfect squares, (), 78-87
[5] Furst, M.L.; Saxe, J.B.; Sipser, M., Parity, circuits, and the polynomial time hierarchy, (), 260-270
[6] Masek, W., A fast algorithm for the string editing problem and decision graph complexity, ()
[7] Nechiporuk, E.I., A Boolean function, Sov. math. dokl., 7, 999-1000, (1966) · Zbl 0161.00901
[8] Pudlák, P., A lower bound on complexity of branching programs, (1983), Univ. Prague, preprint · Zbl 0572.68033
[9] Pudlák, P.; Zák, S., Space complexity of computations, (1983), Univ. Prague, preprint
[10] Wegener, I., Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Inform. and control, 62, 129-143, (1984) · Zbl 0592.94025
[11] \scI. Wegener, On the complexity of branching programs and decision trees for clique functions, J. Assoc. Comput. Mach., in press. · Zbl 0621.68028
[12] Yao, A.C., Lower bounds by probabilistic arguments, (), 420-428
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.