Počet záznamů: 1
Incremental Branching Programs
- 1.
SYSNO ASEP 0318538 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Incremental Branching Programs Překlad názvu Inkrementální rozhodovací programy Tvůrce(i) Gál, A. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
McKenzie, P. (CA)Zdroj.dok. Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 43, č. 2 (2008), s. 159-184Poč.str. 26 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova branching programs ; models of computation ; lower bounds Vědní obor RIV BA - Obecná matematika CEP GP201/07/P276 GA ČR - Grantová agentura ČR GA201/05/0124 GA ČR - Grantová agentura ČR CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000254777600005 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2009
Počet záznamů: 1