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 Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity
Zitatschlüssel B-On-Implications-Between-P-Np-Hypotheses-Decision-Versus-Computation-In-Algebraic-Complexity
Autor Peter Bürgisser
Buchtitel Proc. 26th Symposium on Mathematical Foundations of Computer Science
Seiten 3-17
Jahr 2001
Adresse Marianske Lazne
Nummer 2136
Notiz (invited paper)
Verlag Springer Verlag
Serie Lecture Notes in Computer Science
Zusammenfassung Several models of $NP$-completeness in an algebraic framework of computation have been proposed in the past, each of them hinging on a fundamental hypothesis of type $P\ne NP$. We first survey some known implications between such hypotheses and then describe attempts to establish further connections. This leads us to the problem of relating the complexity of computational and decisional tasks and naturally raises the question about the connection of the complexity of a polynomial with those of its factors. After reviewing what is known with this respect, we discuss a new result involving a concept of approximative complexity.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe