Die Bedeutung kryptographischer Falltürfunktionen für Algorithmisches Lernen
Die Bedeutung kryptographischer Falltürfunktionen für Algorithmisches Lernen
Autor: Guido Kehrle1. Gutachter: Johannes Köbler (Betreuer)
2. Gutachter: Uwe Schöning
Zusammenfassung: Diese Arbeit beschäftigt sich mit den Zusammenhängen von Kryptographie und Erlernbarkeitstheorie. Hierbei werden vorwiegend die Auswirkungen von kryptographischen Annahmen auf das effiziente Erlernen von Konzeptklassen untersucht.
Es werden zunächst die komplexitätstheoretischen Grundlagen erläutert. Im Anschluß an eine kurze Einführung in die Kryptographie und die Erlernbarkeitstheorie weisen wir die nichteffiziente Erlernbarkeit von Konzeptklassen auf der Grundlage kryptographischer Annahmen nach. Wir sehen dabei, daß diese Resultate Auswirkungen auf die Approximierbarkeit von Optimierungsproblemen haben. Danach zeigen wir - ebenfalls auf der Grundlage von kryptographischen Annahmen - daß viele Klassen auch durch eine erweiterte Erlernbarkeitsdefinition nicht effizient erlernbar werden. Schließlich weisen wir noch nach, daß sich durch die Verwendung dieser erweiterten Erlernbarkeitsdefinition beim effizienten Erlernen von einigen Konzeptklassen, deren Erlernbarkeitsstatus noch offen ist, kein Vorteil ergibt. Abschließend untersuchen wir, welche Schlüsse sich von Erlernbarkeitsresultaten auf kryptographische Systeme ziehen lassen.
Download: Die Bedeutung kryptographischer Falltürfunktionen für Algorithmisches Lernen