Inkrementální rozhodovací programy

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F06%3A00041386" target="_blank" >RIV/67985840:_____/06:00041386 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Incremental Branching Programs ( Extended Abstract )

Popis výsledku v původním jazyce

In this paper we propose the study of a new model of restricted branching programs which we call incremental branching programs. This in line which 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 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 generalvariant of incremental branching programs. Some of our techniques also yield exponential lower bounds without the incrementality restriction, under some other conditions.

Název v anglickém jazyce

Incremental Branching Programs ( Extended Abstract )

Popis výsledku anglicky

In this paper we propose the study of a new model of restricted branching programs which we call incremental branching programs. This in line which 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 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 generalvariant of incremental branching programs. Some of our techniques also yield exponential lower bounds without the incrementality restriction, under some other conditions.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2006

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of International Computer Science Symposium in Russia

ISBN

3-540-34166-8

ISSN

—

e-ISSN

—

Počet stran výsledku

13

Strana od-do

178-190

Název nakladatele

Springer Verlag

Místo vydání

Berlin

Místo konání akce

Sankt Petersburg

Datum konání akce

8. 6. 2006

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—