Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials | springerprofessional.de

Springer Professional

nach oben

Erschienen in:

2001 | OriginalPaper | Buchkapitel

Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials

verfasst von : Markus Bläser

Erschienen in: Computing and Combinatorics

Verlag: Springer Berlin Heidelberg

Enthalten in: Professional Book Archive

Zugang erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

We prove that the families matrix powering, iterated matrix product, and adjoint matrix are VQP-complete, where VQP denotes Valiant’s class of quasipolynomial-computable families of multivariate polynomials. This proves a conjecture by Bürgisser [3, Conjecture 8.1].

Nächstes Kapitel Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n 4.03)

Titel: Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials
verfasst von: Markus Bläser
Verlag: Springer Berlin Heidelberg
Buch: Computing and Combinatorics
Print ISBN: 978-3-540-42494-9

Electronic ISBN: 978-3-540-44679-8

Copyright-Jahr: 2001
DOI: https://doi.org/10.1007/3-540-44679-6_1

Springer Professional

Premium Partner