2026-07-19T21:09:59Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:623
2024-03-06T11:06:46Z
ddc:004
open_access
Incremental branching programs
Gál, Anna
McKenzie, Pierre
Koucký, Michal
Complexity theory
branching programs
logarithmic space
marking machines
We propose a new model of restricted branching programs
which we call {em incremental branching programs}.
We show that {em syntactic}
incremental branching programs capture previously studied
structured models of computation for the problem GEN, namely marking
machines [Cook74].
and Poon's extension [Poon93] of jumping automata
on graphs [CookRackoff80].
We then prove
exponential size lower bounds for our syntactic incremental model,
and for some other restricted branching program models as well.
We further show that nondeterministic syntactic incremental
branching programs are
provably stronger than their deterministic counterpart when solving a
natural NL-complete GEN subproblem.
It remains open if syntactic incremental branching programs are as powerful
as unrestricted branching programs for GEN problems.
Joint work with Anna Gál and Michal Koucký
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Anna Gál and Pierre McKenzie and Michal Koucký
2006
Is Part Of Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/DagSemProc.06111.10
urn:nbn:de:0030-drops-6230
https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.10
eng
https://creativecommons.org/licenses/by/4.0/legalcode