Lower bound for deterministic semantic-incremental branching programs solving GEN

Details Lower bound for deterministic semantic-incremental branching programs solving GEN Lower bound for deterministic semantic-incremental branching programs solving GEN

2011-01-14

arxiv.org/abs/1101.2705v1

Computer Science

Computational Complexity

9 pages

Scientific paper

We answer a problem posed in (G\'al, Kouck\'y, McKenzie 2008) regarding a restricted model of small-space computation, tailored for solving the GEN problem. They define two variants of "incremental branching programs", the syntactic variant defined by a restriction on the graph-theoretic paths in the program, and the more-general semantic variant in which the same restriction is enforced only on the consistent paths - those that are followed by at least one input. They show that exponential size is required for the syntactic variant, but leave open the problem of superpolynomial lower bounds for the semantic variant. Here we give an exponential lower bound for the semantic variant by generalizing lower bound arguments, from earlier work, for a similar restricted model tailored for solving a special case of GEN called Tree Evaluation.

Affiliated with

Also associated with

No associations

Rating

Lower bound for deterministic semantic-incremental branching programs solving GEN does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower bound for deterministic semantic-incremental branching programs solving GEN, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bound for deterministic semantic-incremental branching programs solving GEN will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78410