direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Dr. Stefan Mengel


CRIL-CNRS/Université d'Artois
Faculté des Sciences Jean Perrin
rue Jean Souvraz, S.P. 18
F-62307 LENS Cedex
Persönliche Homepage

Publikationen in der Arbeitsgruppe

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

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.