Modified Branching Programs and Their Computational Power

Branching Programs are, besides Boolean circuits, the most important nonuniform model of computation. This volume gives a survey of the latest research in this field. It presents a branching program-based approach to complexity theory. Starting with a definition of branching programs and a review of the former research, nondeterministic branching programs are introduced and investigated, thus allowing the description of some fundamental complexity classes. The book then concentrates on the new concept of Omega-branching programs. Apart from the usual binary tests they contain features for evaluating certain elementary Boolean functions and are suited for characterizing space-bounded complexity classes. By means of these characterizations the author demonstrates the separation of some restricted complexity classes. In the appendix a number of extremely restricted graph-accessibility problems are given, which are, due to the branching program descriptions in chapters 1-3, p-projection complete in the classes under consideration.

Autorentext
Dr. sc. nat. Christoph Meinel (1954) ist Direktor und Geschäftsführer des Hasso-Plattner-Instituts für Softwaresystemtechnik GmbH (HPI) und ordentlicher Professor (C4) für Internet-Technologien und Systeme. Er hat Mathematik und Informatik an der Humboldt-Universität in Berlin studiert, dort 1981 promoviert und sich 1988 an der Akademie der Wissenschaften in Berlin habilitiert. Er wurde 1992 zum ordentlichen Professor (C4) für Informatik an die Univ. Trier berufen und hat dort in den Jahren 1998-2002 neben seinem Lehrstuhl das von der Fraunhofer-Gesellschaft betreute Institut für Telematik e.V. geleitet. Seit 2004 ist er Direktor und Geschäftsführer des HPIs und hat einen Lehrstuhl (C4) für Internet-Technologien und Systeme an der Universität Potsdam. Neben seiner Lehrtätigkeit in Potsdam ist er Gastprofessor an der Univ. Luxembourg (Luxembourg) und an der TU Peking (China) und als Programmdirektor des HPI-Stanford Forschungsprogramms zum Design Thinking Research tätig. Christoph Meinel ist Autor bzw. Co-Autor und Inhaber internationaler Patente. Seine aktuellen Forschungsinteressen liegen in den Bereichen IT-Sicherheit, Teleteaching, Semantic/Social Web und e-Health. Er war wissenschaftlich aktiv auch auf dem Gebiet der Komplexitätstheorie und hat (BDD-basierte) Datenstrukturen und effiziente Algorithmen untersucht und entworfen. Er ist Chairman des 2007 gegründeten deutschen IPv6-Rats, Herausgeber von ECCC - Electronic Colloquiums on Computational Complexity, des IT-Gipfelblog und des tele-TASK-Archivs. 1996-2007 gehörte er dem Direktorium des IBFI Schloss Dagstuhl an und war Sprecher der GI-Fachgruppe 'Komplexität'. Er hat in einer großen Zahl internationaler Programm-Komitees mitgewirkt, diverse Konferenzen und Symposien veranstaltet und ist in wissenschaftlichen Aufsichtsräten aktiv.

Inhalt
Preliminaries.- Branching programs and their computational power.- Nondeterministic branching programs.- ?=branching programs and theirs computational power.