TU Berlin

Fachgebiet Algorithmische AlgebraRefereed Contributions

Page Content

to Navigation

There is no English translation for this web page.

Refereed Contributions

Arithmetic Branching Programs with Memory
Citation key M-Arithmetic-Branching-Programs-With-Memory
Author Stefan Mengel
Title of Book Mathematical foundations of computer science 2013
Pages 667-678
Year 2013
DOI 10.1007/978-3-642-40313-2_59
Volume 8087
Publisher Springer, Heidelberg
Abstract We extend the well known characterization of VP_ws as the class of polynomials computed by polynomial size arithmetic branching programs to other complexity classes. In order to do so we add additional memory to the computation of branching programs to make them more expressive. We show that allowing different types of memory in branching programs increases the computational power even for constant width programs. In particular, this leads to very natural and robust characterizations of VP and VNP by branching programs with memory.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe