Discrete Mathematics & Theoretical Computer Science
Volume 3 n° 3 (1999), pp. 73-94
| author: | Peter Bürgisser |
|---|---|
| title: | On the Structure of Valiant's Complexity Classes |
| keywords: | Structural complexity, Algebraic theories of NP-completeness diagonalization, Poset of degrees. |
| 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 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 andVNPh and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VPh = VNPh. |
| reference: | Peter Bürgisser (1999), On the Structure of Valiant's Complexity Classes, Discrete Mathematics and Theoretical Computer Science 3, pp. 73-94 |
| ps.gz-source: | dm030301.ps.gz (66 K) |
| ps-source: | dm030301.ps (194 K) |
| pdf-source: | dm030301.pdf (154 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Tue Jun 29 14:25:43 MEST 1999 by gustedt