A read-once lower bound and a (1,+k)-hierarchy for branching programs

✍ Scribed by P. Savický; S. Žák

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 143 KB
• Volume: 238
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00219-9

✦ Synopsis

Branching programs (b. p.'s) or decision diagrams are a general graph-based model of sequential computation. The b. p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for di erent kinds of restricted b. p.'s are intensively investigated. An important restriction are the so-called k-b. p.'s, where each computation reads each input variable at most k times.

Although exponential lower bounds have been proven for syntactic k-b.p.'s, this is not true for general (nonsyntactic) k-b.p.'s, even for k = 2. Therefore, the so-called (1; +k)-b. p.'s are investigated.

For some explicit functions, exponential lower bounds for (1; +k)-b. p.'s are known. We prove that the hierarchy of (1; +k)-b. p.'s w.r.t. k is strict. More exactly, we present (multipointer) functions f n;k which are polynomially easy for (1; +k)-b. p.'s, but exponentially hard for (1; +(k-1))-b. p.'s for k6 1 2 n 1=6 = log 1=3 n. This is a generalization of a similar result of Sieling [20] for syntactic (1; +k)-branching programs.

As a by-product, we prove a lower bound of 2 n-3 √ n for an explicit (pointer) function in P.