English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman, and Santhanam introduced the Tree Evaluation Problem (TEP). For fixed integers h and k > 0, FTh (k) is given as a complete, rooted binary tree of height h, in which each root node is associated with a function from [k](2) to [k], and each leaf node with a number in [k]. The value of an internal node v is defined naturally; that is, if it has a function f and the values of its two child nodes are a and b, then the value of v is f (a, b). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P, and, if we could prove that any branching program solving FTh (k) needs at least k(r) (h) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The mentioned authors introduced a restriction called thrifty against the structure of BP's (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs Omega(k(h)) states. This article proves a similar lower bound for read-once branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.

Read-Once Branching Programs for Tree Evaluation Problems