Universit"at Trier Fachbereich IV - Informatik

Christoph Meinel: Schaltkreiskomplexit"atstheorie

Vorlesungsskript WS 1992/93 "uberarbeitete Version SS 1995

Inhaltsverzeichnis 1 Einf"uhrung 1

1.1 Grundbegriffe der Komplexit"atstheorie : : : : : : : : : : : : : : : : : : : : 1

1.1.1 Probleme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.1.2 Berechnungsmodelle : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Boolesche Funktionen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5

1.2.1 Spezielle Funktionen aus IB0 [ IB1 [ IB2 : : : : : : : : : : : : : : : : 6 1.2.2 Boolesche Algebra : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 1.2.3 Geometrische Veranschaulichung Boolescher Funktionen : : : : : : 9 1.2.4 Monotone und symmetrische Boolesche Funktionen : : : : : : : : : 10 1.2.5 Kanonische disjunktive und konjunktive Normalform : : : : : : : : 11 1.2.6 Ring-Summen-Entwicklung (RSE) : : : : : : : : : : : : : : : : : : 15

2 Boolesche Schaltkreise 17

2.1 Modell : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 2.2 Komplexit"atsmasse f"ur Schaltkreise : : : : : : : : : : : : : : : : : : : : : : 19 2.3 Schaltkreise mit beschr"anktem fan-out : : : : : : : : : : : : : : : : : : : : 20 2.4 Vergleich verschiedener \Omega -Schaltkreise : : : : : : : : : : : : : : : : : : : : 21 2.5 Schaltkreiskomplexit"atsklassen : : : : : : : : : : : : : : : : : : : : : : : : : 25 2.6 Simulation von Turing-Maschinen durch Schaltkreise : : : : : : : : : : : : 28 2.7 Simulation von Schaltkreisen durch Turing-Maschinen : : : : : : : : : : : 31 2.8 Effiziente Schaltkreise f"ur einige wichtige Funktionen : : : : : : : : : : : : 35

2.8.1 Addition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35 2.8.2 Multiplikation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 45 2.8.3 Symmetrische Funktionen : : : : : : : : : : : : : : : : : : : : : : : 49 2.8.4 Matrixmultiplikation : : : : : : : : : : : : : : : : : : : : : : : : : : 50 2.9 Typische Schaltkreisgr"osse : : : : : : : : : : : : : : : : : : : : : : : : : : : 53 2.10 Untere Schranken f"ur die Schaltkreisgr"osse : : : : : : : : : : : : : : : : : : 57

3 Boolesche Formeln 64

3.1 Modell : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 3.2 Satz von Spira : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 66 3.3 Typische Formelgr"osse : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68 3.4 Untere Schranken f"ur die Formelgr"osse : : : : : : : : : : : : : : : : : : : : : 69

INHALTSVERZEICHNIS ii 4 Schaltkreise beschr"ankter Tiefe 75

4.1 Modell : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 4.2 Exponentielle untere Schranke f"ur U -Schaltkreise beschr"ankter Tiefe : : : : 76 4.3 Exponentielle untere Schranke f"ur Z-Schaltkreise beschr"ankter Tiefe : : : 79 4.4 Reduktionen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80

5 Bin"are Entscheidungsgraphen 83

5.1 Modell : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 83 5.2 Simulation von Branching-Programmen durch Turing Maschinen und umgekehrt : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86 5.3 Verh"altnis Branching-Programm und Schaltkreis : : : : : : : : : : : : : : : 87 5.4 Typische Branching-Programm-Gr"ossen : : : : : : : : : : : : : : : : : : : : 89 5.5 Untere Schranke f"ur Branching-Programme : : : : : : : : : : : : : : : : : 89 5.6 Entscheidungsb"aume : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90 5.7 Read-Once-Only Branching Programme : : : : : : : : : : : : : : : : : : : 92 5.8 Branching-Programm beschr"ankter Weite : : : : : : : : : : : : : : : : : : 96

Kapitel 1 Einf"uhrung

1.1 Grundbegriffe der Komplexit"atstheorie

ffl Die Komplexit"atstheorie versucht algorithmisch l"osbare Probleme ("Entscheidungsprobleme" bzw. "Sprachen") gem"ass ihrem Bedarf an Berechnungsressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, : : : ) zu klassifizieren.