Polynomial query complexity in algorithmic learning theory

• Applicant: Professor Dr. Johannes Köbler
• Subject Area: Theoretical Computer Science
• Term: from 1999 to 2005
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5190858

Es sollen deterministische und probabilistische Lernalgorithmen vorwiegend im Kontext von Angluins Modell des 'Exakten QueryLernens' 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 erlernbar sind und unter welchen Voraussetzungen hieraus bereits auf die Erlernbarkeit in Polynomialzeit geschlossen werden kann. Umgekehrt erwarten wir, neue Anwendungen von in der Erlernbarkeitstheorie entwickelten Lösungsstrategien in der Komplexitätstheorie zu finden. Des weiteren soll der Ressourcenverbrauch von Lernalgorithmen im average-case untersucht werden, da eine worst-case-Analyse in manchen Fällen für die Praxis nur wenig aussagekräftig ist. Dabei erwarten wir, neue Zusammenhänge zwischen offenen Fragen der Komplexitätstheorie und Fragestellungen der Erlernbarkeitstheorie herstellen zu können.

• DFG Programme: Research Grants