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

• Antragsteller: Professor Dr. Juraj Hromkovic
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2002 bis 2004
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5348233

Die Hauptrichtungen unserer Untersuchungen sind: Ein Vergleich der Berechnungsstärke und der Beschreibungskomplexität von deterministischen, Las Vegas und allgemeinen probabilistischen und (selbst-verifizierenden) nichtdeterministischen Modellen. Dabei gehen wir von einfachen zu komplexeren Modellen vor. 2. Die Anzahl der Zufallsbits und die Anzahl der nichtdeterministischen Entscheidungen sind wichtige Ressourcen randomisierter und nichtdeministischer Berechnungen. Wir wollen diese Ressourcen als Komplexitätsmaße im Trade-Off mit der Berechnungskomplexität betrachten. 3. Die zentrale Methode unserer Untersuchungen basiert auf der Anwendung der Kommunikationskomplexität. Unser Ansatz besteht in der Modellierung vorgegebener Maschinenmodelle durch 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