Multiplikation in eingeschränkten Branchingprogrammmodellen

Abstract

und Ausblick Wir können nicht erwarten, auf die eingangs gestellte Frage nach der Komplexität der Multiplikation in naher Zukunft für irgendein allgemeines Rechenmodell wie Schaltkreise oder Branchingprogramme eine vollständige Antwort zu finden. Wir können aber versuchen, nach und nach zu umfassenderen Erkenntnissen über die Multiplikation zu gelangen und neue Techniken zum Nachweis oberer und unterer Schranken zu entwickeln, um auf diese Weise die Komplexität der Multiplikation besser einzugrenzen. Die Ergebnisse der Dissertation stellen einen weiteren Schritt in diese Richtung dar. Dass dies nicht der letzte war, zeichnet sich schon an einer Reihe weiterführender Erkenntnisse über die Branchingprogrammkomplexität der Multiplikation ab. So konnten z. B. in [BWW02] und [BW] exponentielle untere Schranken in weiteren eingeschränkten nichtdeterministischen FBDD-Modellen nachgewiesen werden und kürzlich zeigten Sauerhoff und Woelfel exponentielle untere Schranken für nichtdeterministische Branchingprogramme, bei denen jede Variable auf jedem graphtheoretischen Pfad konstant oft vorkommen darf [SW03]. Literatur [Br85] Bryant, R. E.: Symbolic manipulation of boolean functions using a graphical representation. Proceedings of the 22nd ACM/IEEE Design Automation Conference (DAC). S. 688-694. 1985. [Br86] Bryant, R. E.: Graph-ba