Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-136 | 14th November 2005 00:00

Incremental branching programs


Authors: Anna Gal, Michal Koucky, Pierre McKenzie
Publication: 22nd November 2005 15:36
Downloads: 3180


In this paper we propose the study of a new model of restricted
branching programs which we call incremental branching programs.
This is in line with the program proposed by Cook in 1974 as an
approach for separating the class of problems solvable in logarithmic
space from problems solvable in polynomial time, focusing on the
P-complete problem GEN. We show that our model captures and possibly
supersedes previously studied structured models of computation
for GEN, namely marking machines Cook (1994) and Poon's (1993) extension
of jumping automata on graphs, that were originally defined by Cook and
Rackoff (1980). We show several exponential lower bounds for variants of
our model although we are unable to prove any strong lower bounds for the
most general variant of incremental branching programs. Some of our
techniques also yield exponential lower bounds without the incrementality
restriction, under some other conditions. It remains open if
incremental branching programs are as powerful as unrestricted
branching programs for GEN problems.

ISSN 1433-8092 | Imprint