direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ehemalige Mitarbeiter

Dr. Stefan Mengel

Lupe

Kontakt
CRIL-CNRS/Université d'Artois
Faculté des Sciences Jean Perrin
rue Jean Souvraz, S.P. 18
F-62307 LENS Cedex
FRANCE
 
Persönliche Homepage
www.cril.univ-artois.fr/~mengel/

Publikationen in der Arbeitsgruppe

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