Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes

Autor:	Guillaume Malod
Rok vydání:	2011
Předmět:	Algebraic cycle Discrete mathematics Function field of an algebraic variety ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Real algebraic geometry Algebraic function Dimension of an algebraic variety Algebraic number Algebraic expression Algebraic element Mathematics
Zdroj:	Fundamentals of Computation Theory ISBN: 9783642229527 FCT
DOI:	10.1007/978-3-642-22953-4_18
Popis:	We study characterizations of algebraic complexity classes by branching programs of possibly exponential size, using a succinctness condition to replace the usual one based on uniformity. We obtain characterizations of VPSPACE, the class corresponding to computations in polynomial space, and observe that algebraic polynomial space can be seen as constant algebraic space with auxiliary polynomial space Boolean computations. We also obtain the first examples of natural complete polynomials for VPSPACE, in particular showing that polynomials like the determinant, the permanent or theHamiltonian become VPSPACE-complete when the matrix is succinctly encoded. Using the same techniques we also characterize VNP. In general, we argue that characterizations by branching programs apply to different classes, both Boolean and algebraic, with or without uniformity, and thus provide a general and uniform technique in these different settings.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::d2e8fad755a607b785ddc73c93f5a491 https://doi.org/10.1007/978-3-642-22953-4_18 Zobrazit plný text záznamu