@article{B-On-The-Structure-Of-Valiants-Complexity-Classes,
Title = {On the structure of Valiant's complexity classes},
Author = {Peter Bürgisser},
Pages = {73-94},
Year = {1999},
Journal = {Discr. Math. Theoret. Comp. Sci.},
Volume = {3},
Abstract = {In 1979 Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay (1975), Ladner (1975), and Schöning (1982, 1984). We show that if Valiant's hypothesis is true, then there is a $p$-definable family, which is neither $p$-computable nor $VNP$-complete. More generally, we define the posets of $p$-degrees and $c$-degrees of $p$-definable families and prove that any countable poset can embedded in either of them, provided Valiant's hypothesis is true. Moreover, we establish the existence of minimal pairs for $VP$ in $VNP$. Over finite fields, we give a specific example of a family of polynomials which is neither VNP-complete nor p-computable, provided the polynomial hierarchy does not collapse. We define relativized complexity classes $VP^h$ and $VNP^h$ and construct complete families in these classes. Moreover, we prove that there is a $p$-family $h$ satisfying $VP^h=VNP^h$.},
Url = {http://link.springer.com/chapter/10.1007%2FBFb0028561}
}