Die Stärke probabilistischer Berechnungen im Vergleich mit nichtdeterministischen und deterministischen Berechnungen

• Antragsteller: Professor Dr. Georg Schnitger
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2002 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5348237

Randomisierte (zufallsgesteuerte) Algorithmen sind ein fester Bestandteil der Algorithmenfamilie und werden standardmäßig in vielen Software-Produkten eingesetzt. Oft bezeichnet man die Klasse praktisch lösbarer algorithmischer Aufgaben als die Klasse der Aufgaben, die man mit randomisierten Algorithmen effizient lösen kann. Die Bestimmung der tatsächlichen Berechnungsstärke randomisierter Berechnungen ist deshalb eine der zentralen Aufgabenstellungen der Komplexitätstheorie und der Algorithmentheorie. Randomisierte Systeme können wesentlich kompakter als ihre deterministischen Varianten sein, wodurch sie dann letztendlich zuverlässiger als komplexere deterministische Systeme sind. Dieser Aspekt der geringen Beschreibungskomplexität ist neben der Berechnungsstärke von ebenfalls zentraler Relevanz. Die Hauptrichtungen unserer Untersuchung sind: 1. Ein Vergleich der Berechnungsstärke und der Beschreibungskomplexität von deterministischen, probabilistischen und nichtdeterministischen Berechnungsmodellen. Dabei gehen wir von einfacheren Modellen (wie Einweg-Automaten, Zweiweg-Automaten oder Kellerautomaten) zu komplexeren Modellen (wie Branchingprogramme oder Kommunikationsmodelle) vor. 2. Die Anzahl der Zufallsbits und die Anzahl der nichtdeterministischen Entscheidungen sind wichtige Ressourcen randomisierter und nichtdeterministischer Berechnungen. Wir wollen diese Ressourcen als Komplexitätsmaße im Trade-Off mit der Berechnungskomplexität (oder der Beschreibungskomplexität) betrachten. 3. Eine zentrale Methode unserer Untersuchungen basiert auf der Anwendung der Kommunikationskomplexität. Unser Ansatz besteht in der Modellierung vorgegebener Maschinenmodelle durch (nicht-standard) Kommunikationsmodelle und einer anschließenden Analyse des jeweiligen Kommunikationsmodells. Die Entwicklung hinreichend mächtiger, aber noch analysierbarer Kommunikationsmodelle steht deshalb im Vordergrund.

• DFG-Verfahren: Sachbeihilfen