On the Structure of Valiant's Complexity Classes
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
1999-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/99 |
| _version_ | 1818230938239238144 |
|---|---|
| author | Peter Bürgisser |
| author_facet | Peter Bürgisser |
| author_sort | Peter Bürgisser |
| collection | DOAJ |
| description | 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 VPin 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. |
| first_indexed | 2024-12-12T10:42:27Z |
| format | Article |
| id | doaj.art-72cc69d782394a1fb7acc4a44730a7a9 |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-12-12T10:42:27Z |
| publishDate | 1999-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-72cc69d782394a1fb7acc4a44730a7a92022-12-22T00:27:01ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80501999-12-0133On the Structure of Valiant's Complexity ClassesPeter BürgisserIn 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 VPin 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.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/99 |
| spellingShingle | Peter Bürgisser On the Structure of Valiant's Complexity Classes Discrete Mathematics & Theoretical Computer Science |
| title | On the Structure of Valiant's Complexity Classes |
| title_full | On the Structure of Valiant's Complexity Classes |
| title_fullStr | On the Structure of Valiant's Complexity Classes |
| title_full_unstemmed | On the Structure of Valiant's Complexity Classes |
| title_short | On the Structure of Valiant's Complexity Classes |
| title_sort | on the structure of valiant s complexity classes |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/99 |
| work_keys_str_mv | AT peterburgisser onthestructureofvaliantscomplexityclasses |