Number of the records: 1
Incremental branching programs
- 1.
SYSNO ASEP 0089738 Document Type O - Others R&D Document Type Others Title Incremental branching programs Author(s) Gál, A. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
McKenzie, P. (CA)Year of issue 2005 Series TR05-136 Number of pages 10 s. Language eng - English Country CZ - Czech Republic Keywords branching programs ; models of computation ; lower bounds Subject RIV BA - General Mathematics R&D Projects 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) GA201/05/0124 GA ČR - Czech Science Foundation (CSF) CEZ AV0Z10190503 - MU-W (2005-2011) Annotation 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 solvabel 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2008
Number of the records: 1