direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

On the structure of Valiant's complexity classes
Zitatschlüssel B-On-The-Structure-Of-Valiants-Complexity-Classes
Autor Peter Bürgisser
Seiten 73-94
Jahr 1999
Journal Discr. Math. Theoret. Comp. Sci.
Jahrgang 3
Zusammenfassung In 1979 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 (1975), Ladner (1975), and Schöning (1982, 1984). 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 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 $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$.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe