In [25,27] Valiant developed an lagebraic analogue of the theory of NP-completeness for computations with polynomials over a field. We further develop this theory in the spirit ofstructual complexity and obtain analogues of well-known results by Baker, Gill, and Solovay [1], Ladner [18], adn Schoning [23,24]. We show that if Valiant's hypothesis is true, then there is a p-definable family, which is neither p-computable nor VNP-compelte. More generally, we define the psets of p-degrees and c-degrees fo p-definable families and prove that any countable poset can embeeded in either of them, provided Valiant's hypothesis is true. Morvover, we establish the existence of minimal pairs for VP in VNP. Over finite fields, we give a specific exampel ofa familty fo polynomials which is neither VNP-complete nor p-computable, provided the polynomial hierarchy does not collapse. We define relativized complexity classes VP sup h and VNP sup h and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VP sup h=VNP sup h.
展开▼
