Polynomielle Fragekomplexität beim Algorithmischen Lernen I


Es sollen deterministische und probabilistische Lernalgorithmen - vorwiegend im Kontext von Angluins Modell des "Exakten Query-Lernens" - konzipiert und ihre Komplexität analysiert werden. Obwohl für eine Reihe von konkreten Konzeptklassen effiziente Lernalgorithmen bekannt sind, ist die effiziente Erlernbarkeit wichtiger Konzeptklassen wie etwa boolescher Schaltkreise weitgehend offen. Um diese und ähnliche Fragen einer Lösung näher zu bringen, soll systematisch untersucht werden, welche Konzeptklassen mit einer polynomiell beschränkten Anzahl von Fragen (unterschiedlicher Typen) erlernbar sind, und unter welchen Voraussetzungen hieraus bereits auf die Erlernbarkeit in Polynomialzeit geschlossen werden kann.


Projektleitung
Köbler, Johannes Prof. Dr. (Details) (Algorithmen und Komplexität II)

Laufzeit
Projektstart: 12/1999
Projektende: 10/2001

Forschungsfelder
Algorithmisches Lernen, Komplexitätstheorie, Kryptographie

Zuletzt aktualisiert 2020-11-03 um 23:12