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

• Applicant: Professor Dr. Juraj Hromkovic
• Subject Area: Theoretical Computer Science
• Term: from 2002 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants