Počet záznamů: 1
Incremental branching programs
- 1.
SYSNO ASEP 0089738 Druh ASEP O - Ostatní výsledky Zařazení RIV O - Ostatní Název Incremental branching programs Tvůrce(i) Gál, A. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
McKenzie, P. (CA)Rok vydání 2005 Edice TR05-136 Poč.str. 10 s. Jazyk dok. eng - angličtina Země vyd. CZ - Česká republika Klíč. slova branching programs ; models of computation ; lower bounds Vědní obor RIV BA - Obecná matematika CEP 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy GA201/05/0124 GA ČR - Grantová agentura ČR CEZ AV0Z10190503 - MU-W (2005-2011) Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2008
Počet záznamů: 1