Campus Event Calendar
Event Entry
What and Who
Quantenrechner und polynomiale Berechenbarkeit
Alexander Bockmayr
Max-Planck-Institut für Informatik
Antrittsvorlesung
AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 7 June 96
16:00
60 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
Auf der Grundlage der Quantenmechanik wurden in den vergangenen Jahren
neue Rechnermodelle entwickelt, die im Hinblick auf polynomiale
Berechenbarkeit möglicherweise mächtiger sind als klassische
Turingmaschinen. Das Problem der Primfaktorzerlegung läßt sich auf
einem Quantenrechner in polynomialer Zeit lösen, während alle dafür
bisher bekannten Verfahren auf herkömmlichen Rechnern exponentiell
sind. Falls es gelingt, Quantenrechner physikalisch zu realisieren,
würde dies den Begriff der polynomialen Berechenbarkeit ebenso wie die
Sicherheit heutiger Kryptosysteme grundsätzlich in Frage stellen.
neue Rechnermodelle entwickelt, die im Hinblick auf polynomiale
Berechenbarkeit möglicherweise mächtiger sind als klassische
Turingmaschinen. Das Problem der Primfaktorzerlegung läßt sich auf
einem Quantenrechner in polynomialer Zeit lösen, während alle dafür
bisher bekannten Verfahren auf herkömmlichen Rechnern exponentiell
sind. Falls es gelingt, Quantenrechner physikalisch zu realisieren,
würde dies den Begriff der polynomialen Berechenbarkeit ebenso wie die
Sicherheit heutiger Kryptosysteme grundsätzlich in Frage stellen.
Contact
--email hidden
passcode not visible
logged in users only