TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

On the structure of Valiant's complexity classes
Zitatschlüssel B-On-The-Structure-Of-Valiants-Complexity-Classes-1
Autor Peter Bürgisser
Buchtitel In Proc. 15th Symposium on Theoretical Aspects of Computer Science
Seiten 194-204
Jahr 1998
Nummer 1373
Verlag Springer Verlag
Serie Lecture Notes in Computer Science
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 Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe