99h:68051 68Q15 (68Q05)
Bürgisser, Peter (CH-ZRCH)
On the structure of Valiant's complexity classes. (English. English summary)
STACS 98 (Paris, 1998), 194--204,
Lecture Notes in Comput. Sci., 1373,
Springer, Berlin, 1998.

Summary: "L. G. Valiant developed an algebraic analogue of the theory of NP-completeness for computations with polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known theoretical results by T. Baker, J. Gill and R. Solovay [SIAM J. Comput. 4 (1975), no. 4, 431--442; MR 52 #16108], R. E. Ladner [J. Assoc. Comput. Mach. 22 (1975), 155--171; MR 57 #4623], and U. Schoning [Theoret. Comput. Sci. 18 (1982), no. 1, 95--103; MR 83b:68055; Theoret. Comput. Sci. 31 (1984), no. 1-2, 41--48; MR 86d:68028].

"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 ${\rm VP}\sp h$ and ${\rm VNP}\sp h$ and construct complete families in these classes. Moreover, we prove that there is a p-family $h$ satisfying ${\rm VP}\sp h={\rm VNP}\sp h$."

\{For the entire collection see MR 99f:68011.\}

Back