TU Berlin

Fachgebiet Algorithmische AlgebraRefereed Contributions

Inhalt des Dokuments

zur Navigation

Refereed Contributions

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
Zitatschlüssel M-Characterizing-Arithmetic-Circuit-Classes-By-Constraint-Satisfaction-Problems
Autor Stefan Mengel
Buchtitel In Proceedings of ICALP 2011
Seiten 700-711
Jahr 2011
Jahrgang 6755
Verlag Springer
Serie Lecture Notes in Computer Science
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe