direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

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

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe