### On the Structure of Valiant's Complexity Classes

*Peter Bürgisser*

#### Abstract

In 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, Ladner, and Schöning.

We show that if Valiant's hypothesis is true, then there is a p-definable family, which is neither p-computable nor

Over finite fields, we give a

We define relativized complexity classes VPh and VNPh and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VPh = VNPh.

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 be 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 VPh and VNPh and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VPh = VNPh.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page