Incremental Branching Programs

0318538 - MÚ 2009 RIV US eng J - Článek v odborném periodiku
Gál, A. - Koucký, Michal - McKenzie, P.
Incremental Branching Programs.
[Inkrementální rozhodovací programy.]
Theory of Computing Systems. Roč. 43, č. 2 (2008), s. 159-184. ISSN 1432-4350. E-ISSN 1433-0490
Grant CEP: GA ČR GP201/07/P276; GA ČR GA201/05/0124
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: branching programs * models of computation * lower bounds
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.766, rok: 2008

In this paper we propose the study of a new model of restricted branching programs which we call incremental branching programs. This is 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 posssibly 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 outher conditions.

Zavádíme nový typ rozhodovacích programů a dokazujeme pro ně dolní odhady.
Trvalý link: http://hdl.handle.net/11104/0167927