Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22953-4_18 | FCT |
Keywords | Field | DocType |
non-uniform complexity class,exponential size,natural complete polynomial,succinct algebraic,auxiliary polynomial space,different setting,algebraic polynomial space,algebraic complexity class,polynomial space,different class,constant algebraic space,boolean computation | Discrete mathematics,Dimension of an algebraic variety,Combinatorics,Function field of an algebraic variety,Polynomial,Algebraic function,Algebraic element,Algebraic cycle,Algebraic expression,Real algebraic geometry,Mathematics | Conference |
Citations | PageRank | References |
3 | 0.39 | 19 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillaume Malod | 1 | 54 | 4.53 |