TU Berlin

Fachgebiet Algorithmische AlgebraRefereed Contributions

Page Content

to Navigation

There is no English translation for this web page.

Refereed Contributions

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
Citation key M-Characterizing-Arithmetic-Circuit-Classes-By-Constraint-Satisfaction-Problems
Author Stefan Mengel
Title of Book In Proceedings of ICALP 2011
Pages 700-711
Year 2011
Volume 6755
Publisher Springer
Series Lecture Notes in Computer Science
Abstract We explore the expressivity of constraint satisfaction problems (CSPs) in the arithmetic circuit model. While CSPs are known to yield VNP-complete polynomials in the general case, we show that for different restrictions of the structure of the CSPs we get characterizations of different arithmetic circuit classes. In particular we give the first natural non-circuit characterization of VP, the class of polynomial families efficiently computable by arithmetic circuits.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe