Inhalt des Dokuments
In Proceedings
| 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. |
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe
Hilfsfunktionen
Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.