Seminar: Komplexität Boolescher Funktionen

Allgemeine Schaltkreise II

Obere und untere Schranken

Ausarbeitung von

Michael Savoric

---

Allgemeine Schaltkreise II

Einleitung

Einleitung

Ein

Boolescher Schaltkreis

S (im folgenden nur Schaltkreis genannt) ist ein gerichteter

azyklischer Graph. Die Knoten von S mit dem Eingangsgrad (engl.

fan-in

) 0 sind die

Eingaben

(Variablen oder die Konstanten 0 und 1). Die Knoten von S mit einem Eingangsgrad k > 0 sind

die

Gatter

. Sie repräsentieren eine Boolesche Funktion mit k Eingaben. Einer der Knoten von S

liefert die

Ausgabe

des Schaltkreises. Als n(S) bezeichnet man die Anzahl der verschiedenen

Variablen des Schaltkreises S. Die

Größe

(oder

Komplexität

) von S, C(S), ist die Anzahl der

Gatter von S. Die

Tiefe

von S, D(S), ist die maximale Länge eines Pfades von der Eingabe zur

Ausgabe.

Ein Schaltkreis S repräsentiert auf natürliche Weise eine

Boolesche Funktion

=

f :

{ }

1

,

0

n(S ) n

{ }

1

,

0

.

Die Menge aller Booleschen Funktionen mit n Variablen bezeichnet man als

B

. Für Boolesche

n

Funktionen f B existieren 2n verschiedene Eingaben, wobei jede dieser Eingaben entweder auf

n

0 oder auf 1 abgebildet werden kann. Es gilt daher die folgende Gleichung:

n

2

B

=

2

n

Um Aussagen über die Komplexität einer beliebigen Booleschen Funktion f machen zu

können, definiert man C(f) als die Größe des kleinsten Schaltkreises, der f berechnet, d.h.

(

C f )

=

min

{

C(S)

f

berechnet

S

:

}

Die Komplexität einer Klasse von Booleschen Funktionen ist gleich der Komplexität der

härtesten Booleschen Funktion in dieser Klasse. Z.B. gilt für die Komplexität der Klasse der

Booleschen Funktionen mit n Variablen

(

C B )

=

max

(

C f ) f

:

B

n

{

n

}

Das Ziel dieses Seminarvortrages ist es, für beliebige Boolesche Funktionen f mit n Variablen

asymptotische Aussagen über die Größe des kleinsten Schaltkreises, der f berechnet, zu machen.

Dabei werden allgemeine Schaltkreise, also Schaltkreise ohne Einschränkungen bezüglich der

Größe und Tiefe betrachtet. Wenn nichts anderes erwähnt wird, betrachten wir im folgenden B -

2

Schaltkreise, d.h. wir betrachten Schaltkreise, deren Gatter einen fan-in von kleiner gleich 2

haben und alle Booleschen Funktionen aus B berechnen können.

2

Asymptotische Aussagen

Sei f: N N eine Funktion. Dann bezeichnen O(f), (f) und o(f) folgende Mengen von

Funktionen:

O(f )

= {

g : N

N :

c

>

,

0

n

g

mit

(n)

c

f (n

n

alle

für

)

n

0

0

}

(f )

= {

g : N

N :

c

>

,

0

n

g

mit

(n)

c

f (n

n

alle

für

)

n

0

0

}

g(n)

(

o f )

=

g

: N

N : lim

=

0

O(f )

n

f (n)

Wir benutzen die O- bzw. die o-Notation in Beweisen von oberen Schranken und die -Notation

in Beweisen von unteren Schranken.

Seite 2

---

Allgemeine Schaltkreise II

Der Shannon-Effekt

Der Shannon-Effekt

1. Formulierung:

Nahezu alle Booleschen Funktionen mit n Variablen besitzen näherungsweise die gleiche

Komplexität wie die härteste Boolesche Funktion mit n Variablen.

2. Formulierung:

Für nahezu alle Booleschen Funktionen mit n Variablen besitzen optimale Schaltkreise eine

exponentielle Größe bei linearer Tiefe.

Die zweite Formulierung ist der ersten vorzuziehen, da in ihr explizit eine Größen- bzw.

Tiefenaussage über optimale Schaltkreise gemacht wird.

Bevor wir den Shannon-Effekt für die Klasse der Booleschen Funktionen mit n Variablen und

B -Schaltkreise beweisen, verdeutlichen wir uns die Aussage durch ein

Abzählargument

:

2

Einerseits gibt es nicht sehr viele Schaltkreise mit geringer Größe, andererseits existieren sehr

viele Boolesche Funktionen mit n Variablen.

Definition

Die bereits des öfteren benutzte Redewendung "nahezu alle Booleschen Funktionen f besitzen

die Eigenschaft e" bedeutet mathematisch ausgedrückt:

E

= {

f

B

f

:

Eigenschaf

besitzt

n

}

e

t

E

lim

1

n

Bn

Andere Formulierung: Wenn wir n nur genügend groß wählen, dann besitzen vernachlässigbar

wenige Funktionen f die Eigenschaft e nicht.

Seite 3

---

Allgemeine Schaltkreise II

eine untere Schranke für nicht-explizite Probleme

eine untere Schranke für nicht-explizite Probleme

Obwohl wir meistens mit explizit angegebenen Problemen (z.B. die Probleme in P oder NP)

arbeiten, ist es auch sehr wichtig zu wissen, welche Aussagen man über nicht-explizite Probleme

machen kann. Dazu betrachten wir das folgende

Theorem (

in Anlehnung an:

[1], Theorem

2.4.):

Nahezu jede Boolesche Funktion mit n Variablen benötigt Schaltkreise der Größe

(2n/n).

Beweis:

Zuerst zeigen wir, daß die Anzahl der Schaltkreise mit n Variablen und der Größe s nach oben

beschränkt ist durch

{

S :n(S)

=

n, (

C S)

= }

2

s

s

16

(

(s

+

n

+

2) )

.

Jedes Gatter in einem Schaltkreis berechnet eine von |B | = 16 Funktionen mit 2 Eingaben. Jede

2

dieser Eingaben kann entweder ein vorhergehendes Gatter (höchstens s Möglichkeiten), eine

Variable (n Möglichkeiten), oder eine Konstante (2 Möglichkeiten) sein. Demnach haben wir pro

Gatter höchstens 16(s+n+2)2 Möglichkeiten. Faßt man diese Möglichkeiten für alle s Gatter

zusammen, so ergibt sich die obere Schranke.

Um zu der Aussage des Theorems zu gelangen, müssen wir s geeignet wählen und dann

zeigen, daß nur sehr wenige Boolesche Funktionen mit Schaltkreisen der Größe s berechnet

werden können. Wir wählen s = 2n/(10n):

Für s = 2n/(10n) ist die obere Schranke für die Anzahl der Schaltkreise näherungsweise (siehe

mathematischer Anhang) 22n/5 << 22n. Da aber 22n Boolesche Funktionen mit n Variablen

existieren und jede dieser Booleschen Funktionen durch einen anderen Schaltkreis berechnet

wird, benötigt nahezu jede Boolesche Funktion mit n Variablen Schaltkreise mit einer Größe von

mehr als 2n/(10n) Gatter. Damit ist das Theorem bewiesen.

Eine weitere untere Schranke für nicht-explizite Probleme

Im folgenden schätzen wir die Anzahl der verschiedenen Schaltkreise der Größe s ab. Es gilt

das

Lemma ([2], Lemma 4.2.1.):

Höchstens

S(s, n)

=

16s

(s

+

n

+

)

1 2s

s / !

s

Boolesche Funktionen f

B können durch B -Schaltkreise der Größe s berechnet werden.

n

2

Beweis:

Jedes einzelne der s Gatter kann eine der |B | = 16 verschiedenen Booleschen Funktionen mit

2

2 Eingaben berechnen. An jedem der s Gatter gibt es s+n+1 Möglichkeiten der Wahl jedes

Eingangs (die anderen s-1 Gatter, n Variablen und 2 Konstanten). Wir können unter allen

Ausgaben der s Gatter eine Ausgabe als Gesamtausgabe des Schaltkreises wählen. Zuletzt

müssen wir noch berücksichtigen, daß bei unserer Zählung jeder Schaltkreis s!-mal gezählt

Seite 4

---

Allgemeine Schaltkreise II eine weitere untere Schranke für nicht-explizite Probleme

wurde (die s! verschiedenen Möglichkeiten der Numerierung der einzelnen Gatter). Insgesamt

erhalten wir die oben behauptete Schranke.

Theorem ([2], Theorem 4.2.1.):

Für genügend große n haben mindestens

|

B

|

(1-2-r(n)), mit

r(n) = 2n/n

log log n, der

|

B

|

n

2

2

n

Booleschen Funktionen in B eine Schaltkreisgröße von mindestens 2n/n. Vor allem haben nahezu

n

alle Booleschen Funktionen f

B eine Schaltkreisgröße von mindestens 2n/n.

n

Beweis:

Wenn wir s = s(n) = C(B ) setzen, dann können mindestens alle |B | Booleschen Funktionen

n

n

aus B durch einen Schaltkreis der Größe s berechnet werden. Mit Hilfe des gerade bewiesenen

n

Lemmas können wir schließen:

n

s

2s

2

S(s, n)

=

16

(s

+

n

+

)

1

s / !

s

B

=

2

n

Durch Einsetzen der Stirlingschen Näherungsformel

s

+

1 / 2

-

s

!

s

c

s

e

für eine Konstante c > 0 erhalten wir nach Logarithmieren

log S(s, n)

log B

2

2

n

n

s

2

log (s

+

n

+

)

1

+

s

4

+

log s

-

(s

+

1 / 2)

log s

+

s

log e

-

log c

2

2

2

2

2

2

Für ein genügend großes n gilt s n+1 und deshalb

n

s

log s

+

(6

+

log e)

s

+

1 / 2

log s

-

log c

2

2

2

2

2

Für s 2n/n schließen wir

2n / n

(n

-

log n

+

6

+

log e)

+

1 / 2

(n

-

log n)

-

log c

2n

2

2

2

2

2n / n

(6

+

log e

-

log n)

+

1 / 2

(n

-

log n)

-

log c

0

2

2

2

2

was für genügend große n falsch ist. Deshalb gilt für genügend große n

s

=

(

C B )

2n / n

n

Wir können noch mehr beweisen. Wenn wir eine Untermenge B * von B betrachten, so daß

n

n

log B

2n

-

2n / n

log log n :

=

(

a n)

2

n

2

2

können wir in der gleichen Weise zeigen, daß C(B *) 2n/n für genügend große n. Gewöhnlich

n

wählen wir B * als die Menge der 2a(n) Booleschen Funktionen in B mit den kleinsten

n

n

Schaltkreisgrößen. Wenn wir für diese Menge die untere Schranke gezeigt haben, dann besitzen

zwangsläufig alle anderen Booleschen Funktionen in B noch größere Schaltkreise. Damit ist das

n

Theorem bewiesen.

Seite 5

---

Allgemeine Schaltkreise II

eine obere Schranke

Eine obere Schranke

Eine triviale obere Schranke ist n2n+n-1. Beweis: Man kann jede Boolesche Funktion f B

n

in der disjunktiven Normalform (DNF), d.h. als Disjunktion ihrer Minterme, darstellen. Es

existieren maximal 2n verschiedene Minterme, für deren Berechnung wir jeweils genau n-1

UND-Gatter benötigen, wenn wir die Negationen der n Variablen schon vorliegen haben. Es

folgt

C(B )

(n-1 UND-Gatter)

2n+(2n-1 ODER-Gatter)+(n NICHT-Gatter) = n

2n+n-1 Gatter

n

Wir werden im folgenden eine sehr viel bessere obere Schranke beweisen:

Theorem ([2], Theorem 4.2.2.)

:

Es gilt für alle f

B

n

(

C f )

2n / n

+

(

o 2n / n)

Beweis:

Wir betrachten im folgenden 3 verschiedene Beweisansätze, von denen aber letztlich nur der

dritte Ansatz das geforderte Resultat liefern wird.

1. Ansatz:

Wir betrachten dazu eine bekannte Darstellung einer beliebigen Booleschen Funktion f, die

Shannon′sche Entwicklung

: Seien f (i), f (i) B die Booleschen Unterfunktionen von f B für

0

1

n-1

n

x = 0 und x = 1. Es gilt dann die Darstellung

i

i

f

=

(x

f (i) )

(x

f (i) )

i

0

i

1

Für die Unterfunktionen f (i), f (i) B kann die Shannon′sche Entwicklung weiter fortgesetzt

0

1

n-1

werden. Graphisch kann man sich die ersten beiden Shannon′schen Entwicklungsschritte der

Booleschen Funktion f als vollständigen binären Baum der Tiefe 2 vorstellen (mit i j):

Die Boolesche Funktion f B besitzt 2 Boolesche Unterfunktionen aus B , 4 Boolesche

n

n-1

Unterfunktionen aus B , oder allgemein ausgedrückt 2n-k Boolesche Unterfunktionen aus B .

n-2

k

Eine direkte Umsetzung von f in einen sogenannten

dekodierten Schaltkreis

(engl. decoding

circuit) liefert keine effiziente Lösung. Es gilt nämlich die Rekursionsungleichung

(

C B )

2

(

C B

)

-

+

3

n

n 1

(

C B )

=

1

2

mit der Lösung

(

C B )

2n

-

3

n

Dekodierte Schaltkreise sind nur eine theoretische Beschreibungsmöglichkeit. Man kann sie

leicht verbessern, wie wir im nun folgenden 2. Ansatz sehen werden.

Seite 6

---

Allgemeine Schaltkreise II

eine obere Schranke

2. Ansatz:

In diesem Ansatz verwenden wir folgende Ideen:

· Wir berechnen alle 2n-k Booleschen Unterfunktionen von f in B im voraus in unabhängigen

k

Teilschaltkreisen

· Danach führen wir die Shannon′sche Entwicklung bis zur Rekursionstiefe n-k durch

Sei

nun

C*(B ) die Schaltkreiskomplexität für die Berechnung aller Booleschen Funktionen in

k

B . Es gilt analog zur Shannon′schen Entwicklung

k

C

(B )

C

(B

)

-

+

3

B

k

k 1

k

C

(B )

16

2

mit der Lösung

k

k

-

1

2

2

C (B )

3

2

+

6

2

k

Wir benötigen noch das folgende

Lemma

:

Es sind 3

2n-k-3 Gatter zur Berechnung von f ausreichend, wenn die Booleschen Funktionen in

B gegeben sind.

k

Beweis:

Wir betrachten hierfür noch einmal die ersten beiden Entwicklungsschritte der Shannon′schen

Entwicklung von f und den dazugehörenden Entwicklungsbaum (mit i j):

f

=

(x

f (i) )

(x

f (i) )

i

0

i

1

=

(x

((x

f (i)(j) )

(x

f (i)(j) )))

(x

((x

f (i)(j) )

(x

f (i)(j) )))

i

j

00

j

01

i

j

10

j

11

Ein Entwicklungsbaum der Tiefe t besitzt 2t-1 innere Knoten. Pro inneren Knoten benötigt man 3

Gatter (siehe Formel). Setzen wir t = n-k, dann folgt das Lemma.

Es folgt (für beliebiges k)

k

k

-

1

n

-

k

*

n

-

k

2

2

(

C B )

=

3

2

-

3

+

C (B )

3

(2

+

2 )

+

6

2

n

k

Setzt man k = log n-1, dann folgt (siehe mathematischer Anhang)

2

(

C B )

12

2n / n

+

(

o 2n / n)

n

Diese einfachen Ideen haben uns zu Schaltkreisen geführt, deren Größen nur um den Faktor 12

höher liegen als die Größe eines optimalen Schaltkreises. Um aber den Faktor 12 eliminieren zu

können, muß man einen anderen Ansatz wählen, der um einiges komplizierter sein wird.

Seite 7

---

Allgemeine Schaltkreise II

eine obere Schranke

3. Ansatz:

Im folgenden betrachten wir die sogenannte

(k,s)-Lupanov-Darstellung

für Boolesche

Funktionen. Wir stellen die Funktionswerte von f B in einer 2k× 2n-k-Matrix dar.

n

x x

x x

x x

x x

f

=

2k

×

2n

-

k mit x

{ }

1

,

0

x

x

x x

x

x

x x

Dabei stehen jede der 2k Zeilen für genau einen der 2k verschiedenen Werte von (x ,..., x ) und

1

k

jede der 2n-k Spalten für genau einen der 2n-k verschiedenen Werte von (x

,..., x ).

k+1

n

An der Matrixposition x (1 i 2k, 1 j 2n-k) steht genau dann eine 1 (bzw. 0), wenn die

ij

Funktion f auf die von der i-ten Zeile und der j-Spalte repräsentierten Eingabe eine 1 (bzw. 0)

liefert.

Die Zeilen sind in p = 2k/s 2k/s+1 Blöcke A ,..., A unterteilt, so daß A ,..., A s Zeilen

1

p

1

p-1

und A s′ s Zeilen enthält.

p

Wir versuchen nun, einfachere Boolesche Funktionen als f zu finden und f auf einige von

diesen einfacheren Booleschen Funktionen zu reduzieren:

· Sei

f(x

(x

für

)

,..., x )

1

k

f (x)

i

=

A

i

sonst

0

Offensichtlich gilt dann

f (x)

=

f (x)

i

1

i

p

· Sei (für i < p ist w {0,1}s, für i = p ist w {0,1}s′)

B = Menge der Spalten, deren Schnittpunkte mit A gleich w ist

i,w

i

· Sei

Dann

gilt

f (x)

=

f

(x)

i

i,w

w

· Wir betrachten nun die 2k×2n-k-Matrix von f . Alle Zeilen außerhalb von A bestehen nur aus

i,w

i

Nullen, die Zeilen von A haben nur zwei verschiedene Typen von Spalten: w oder Spalten nur

i

aus Nullen. Wir stellen f als Konjunktion von f 1 und f 2 dar mit

i,w

i,w

i,w

1

beliebiges

für

wenn

1

w

j

j

=

(x

und

1

,..., x

) j -

Zeile

te

A

von

f

(x ,..., x )

i,w

1

k

=

1

k

i

sonst

0

2

(x

wenn

1

,..., x )

k 1

+

n

B

f

(x

i ,w

i ,w

k

+

,..., x )

1

n

=

sonst

0

Seite 8

---

Allgemeine Schaltkreise II

eine obere Schranke

Insgesamt erhalten wir die (k,s)-Lupanov-Darstellung

f (x ,..., x )

=

f 1 (x ,..., x )

f 2 (x

,..., x )

1

n

i,w

1

k

i ,w

k

+

1

n

1

i

p w

Wir berechnen f auf folgende Weise:

Schritt 1

:

Wir berechnen mit

O(2k+2n-k)

Gatter alle Minterme von (x ,...,x ) und von (x

,..., x ).

1

k

k+1

n

Schritt 2

:

Wir berechnen alle f 1 mit deren DNF. Die Minterme sind schon berechnet. Weil die Blöcke

i,w

A alle unabhängig voneinander sind, wird jeder Minterm höchstens einmal für ein festes w

i

benötigt. Insgesamt sind daher

2s

2k

Gatter nötig.

Schritt 3

:

Wir berechnen alle f 2 mit deren DNF. Die Minterme sind schon berechnet. Weil die Blöcke

i,w

B für ein festes i alle unabhängig voneinander sind, wird jeder Minterm höchstens einmal

i,w

für ein festes i benötigt. Insgesamt sind

p

2n-k

Gatter nötig.

Schritt 4

:

Es

sind

2p

2s

Gatter ausreichend, um f zu berechnen, wenn alle f 1 und f 2 vorliegen.

i,w

i,w

Die Anzahl der Gatter unseres Schaltkreises kann wegen p 2k/s+1 abgeschätzt werden mit

k

n

-

k

s

+

k

n

n

-

k

k

+

s

+

1

s

+

1

O(2

+

2

)

+

2

+

2 / s

+

2

+

2

/ s

+

2

Wählt man k = 3log n und s = n-5log n, dann erhält man die Aussage des Theorems

2

2

(siehe mathematischer Anhang).

Eine kurze Zusammenfassung

Bis jetzt haben wir gezeigt, daß (nahezu) alle Booleschen Funktionen mit n Variablen durch

Schaltkreise mit mindestens 2n/n und höchstens 2n/n+o(2n/n) Gatter berechnet werden können.

Für große n kann man o(2n/n) in diesem Zusammenhang vernachlässigen. Dann folgt, daß

(nahezu) alle Booleschen Funktionen mit n Variablen die gleiche (exponentielle)

Schaltkreiskomplexität bei linearer Tiefe besitzen. Damit haben wir bewiesen, daß der Shannon-

Effekt für B und B -Schaltkreise gültig ist.

n

2

Seite 9

---

Allgemeine Schaltkreise II

eine untere Schranke für ein explizites Problem

eine untere Schranke für ein explizites Problem

Trotz der Wichtigkeit der unteren Schranken expliziter Probleme in der

Schaltkreiskomplexität sind die besten bis jetzt bekannten unteren Schranken nur linear. Die

Beweise dieser unteren Schranken benutzen die im folgenden erklärte

Gatter-

Eliminationsmethode

:

Ist für eine gefragte Boolesche Funktion ein Schaltkreis gegeben, so wird im allgemeinen eine

Variable (oder eine Menge von Variablen) mit mehreren Gattern verbunden sein. Setzt man nun

diese Variable auf einen konstanten Wert, so werden einige Gatter überflüssig und eliminiert. Bei

wiederholter Anwendung dieser Methode können wir schließen, daß der ursprüngliche

Schaltkreis sehr viele Gatter besaß.

Als Beispiel werden wir die Gatter-Eliminationsmethode an Schwellen-Funktionen (engl.

threshold functions) anwenden. Eine Schwellen-Funktion TH ist folgendermaßen definiert:

k,n

TH

:

k ,

{ }

1

,

0

n

n

{ }

1

,

0

#

falls

1

1

{

x ,..., x

1

n

}

TH

(x

k ,n

=

x ...x )

1

n

=

k

sonst

0

Wir betrachten zur besseren Verständlichkeit des nun folgenden Theorems die vollständige

Basis B = {, , ¬}. Das Theorem verliert seine Gültigkeit aber auch dann nicht, wenn wir als

Basis B wählen. Es gilt das

Theorem ([1], Theorem 2.5.):

2

Für

n

2 benötigt die Boolesche Funktion TH einen Schaltkreis mit einer Mindestgröße von

2,n

2n-4.

Beweis:

Wir beweisen diese Behauptung durch Induktion nach n. Für n = 2 und n = 3 ist die Schranke

trivial. Angenommen, wir besitzen bereits einen optimalen Schaltkreis S für die Boolesche

o

Funktion TH . Ohne Beschränkung der Allgemeinheit nehmen wir an, daß das erste Gatter von

2,n

S die Variablen x und x (mit i j) miteinander verknüpft:

o

i

j

g B

Unter den vier möglichen Wertekombinationen von x und x besitzt die Boolesche Funktion

i

j

TH drei mögliche Boolesche Unterfunktionen:

2,n

x

x

u

i

j

0

0

TH 2,n

-

2

0

1

TH

1,n

-

2

1

0

TH1,n

-

2

1

1

TH 0,n

-

2

Seite 10

---

Allgemeine Schaltkreise II

eine untere Schranke für ein explizites Problem

Es folgt, daß entweder x oder x mit einem anderen Gatter von S verbunden ist. Andernfalls

i

j

o

hätte der Schaltkreis S nur zwei nichtäquivalente Unterfunktionen unter der Wertebelegung von

o

x und x , da nur noch die Ausgabe von g für den restlichen Schaltkreis verfügbar ist.

i

j

Wir nehmen nun an, daß die Variable x mit einem anderen Gatter verbunden ist:

i

g′, g B

Setzen wir x auf 0, dann eliminieren wir dadurch die Notwendigkeit für mindestens zwei Gatter

i

(g und g′) von S , da wir das Ergebnis von g und g′ ohne Kenntnis von x und e berechnen

o

j

können:

x

x

e

x

x

x

x

x

e x

e

¬

x

i

j

i

j

i

j

i

i

i

0

0

0

0

x

0

e

1

j

0

0

1

0

x

0

e

1

j

0

1

0

0

x

0

e

1

j

0

1

1

0

x

0

e

1

j

Die daraus resultierende Boolesche Funktion ist TH

, welche nach der

2,n-1

Induktionsvorraussetzung einen Schaltkreis mit einer Mindestgröße von 2(n-1)-4 benötigt.

Addiert man die zwei eliminierten Gatter zu diesem Wert hinzu, dann zeigt dies, daß S

o

mindestens 2n-4 Gatter benötigt. Damit ist der Induktionsbeweis abgeschlossen.

Bemerkung: Wir haben zwar gezeigt, daß jeder Schaltkreis, der die Funktion TH berechnet,

2,n

mindestens 2n-4 Gatter benötigt, aber wir haben keinen Hinweis für die Konstruktion eines

optimalen Schaltkreises für TH oder auf die tatsächliche Größe dieses Schaltkreises erhalten.

2,n

Seite 11

---

Allgemeine Schaltkreise II

Literaturliste

Literaturliste

[1]

R. Boppana and M. Sipser, The Complexity of Finite Functions, in: Handbook of

Theoretical Computer Science, (J. van Leeuwen, ed.), Elsevier, Amsterdam, The

Netherlands, 1990, pp. 757-804.

[2]

I. Wegener, The Complexity of Boolean Functions, Teubner, Stuttgart, Germany, 1987.

Seite 12

---

Allgemeine Schaltkreise II Mathematischer

Anhang

In die Formel

2

s

16

(

(s

+

n

+

2) )

setzen wir s = 2n/(10n) ein. Es gilt dann die Abschätzung

2

s

2n / 5

16

(

(s

+

n

+

2) )

<

2

Beweis:

(

n

+

+

16

(

2

n

10

/(

)

+

n

+

2

)

n

2

2

n

10

n

20

n

)

2 2 /(10n )

n

2

2 /(10n )

2n /(10n )

=

16

n

10

2n /(10n )

n

16

=

2

+

n

10

+

n

20

2

(

n

2

)

22 /(10n)

n

100

2n /(10n )

16

n

2

2n /(10n)

<

(2

2 )

2

n

100

2n /(10n )

64

n

2n /(5n )

=

(2 )

2

n

100

2n /(10n )

64

2n / 5

=

2

2

n

100

2n / 5

<

2

In die Formel

k

k

-

1

n

-

k

2

2

(

C B )

3

(2

+

2 )

+

6

2

n

setzen wir k = log n -1 ein. Daraus folgt dann

2

(

C B )

12

2n / n

+

(

o 2n / n)

n

Beweis:

Es gilt log n -2 < k log n -1

2

2

Fall 1: n ist eine Zweierpotenz k = log n -1

2

n

-

log n

-

-

+

2

log n

2

1

log n

2

2

(

C B )

3

(2

1

+

22

)

+

6

22

n

log

n

-

1

log

n

-

2

2

2

=

3

(2n

-

log n

+

1

2

+

22

)

+

6

22

=

3

(2

2n / n

+

2n/2 )

+

6

2n/4

=

6

2n / n

+

(

o 2n / n)

Fall 2: n ist keine Zweierpotenz

worst case: n+1 ist eine Zweierpotenz, für große n gilt k log n -2

2

n

-

log n

-

-

+

2

log n

2

1

log n

2

2

(

C B )

3

(2

1

+

22

)

+

6

22

n

log

n

-

2

log

n

-

3

2

2

3

(2n

-

log n

+

2

2

+

22

)

+

6

22

=

3

(4

2n / n

+

2n/4 )

+

6

2n/8

=

12

2n / n

+

(

o 2n / n)

Insgesamt gilt die obere Schranke.

Seite 1

---

Allgemeine Schaltkreise II Mathematischer

Anhang

In die Formel

k

n

-

k

s

+

k

n

n

-

k

k

+

s

+

1

s

+

1

(

C B )

O(2

+

2

)

+

2

+

2 / s

+

2

+

2

/ s

+

2

n

setzen wir k = 3log n und s = n- 5log n ein. Es gilt dann

2

2

(

C B )

2n / n

+

(

o 2n / n)

n

Beweis:

Es gilt 3log n k < 3log n +1, n-5log n -1 < s n-5log n

2

2

2

2

Fall 1: n ist eine Zweierpotenz k = 3log n, s = n-5log n

2

2

(

C B )

O(2k

+

2n

-

k )

+

2s

+

k

+

2n / s

+

2n

-

k

+

2k

+

s

+

1 / s

+

2s

+

1

n

=

O(23 log

n

-

-

+

-

2

+

2n 3 log n

2

)

+

2n 5 log n 3 log n

2

2

+

2n /(n

-

5

log n)

+

2n 3 log n

2

+

2

23 log

n

+

n

-

5

log n

+

1

-

+

2

2

/(n

-

5

log n)

+

2n 5 log n 1

2

2

=

O(n3

+

2n / n3 )

+

2n / n2

+

2n /(n

-

5

log n)

+

2n / n3

+

2

2

2n /(n2 (n

-

5

log n))

+

2

2n / n5

2

=

2n /(n

-

5

log n)

+

(

o 2n / n)

2

<

2n / n

1

(

+

2

(5

log n) / n)

+

(

o 2n / n)

2

=

2n / n

+

(

o 2n / n)

Fall 2: n ist keine Zweierpotenz k 3log n +1, s n-5log n -1

2

2

(

C B )

O(2k

+

2n

-

k )

+

2s

+

k

+

2n / s

+

2n

-

k

+

2k

+

s

+

1 / s

+

2s

+

1

n

=

O(23 log

n

+

1

-

-

-

- +

+

-

+

2

+

2n 3 log n 1

2

)

+

2n 5 log n 1 3 log n 1

2

2

+

2n /(n

-

5

log n

-

)

1

+

2n 3 log n 1

2

+

2

23 log

n

+

1

+

n

-

5 log

n 1

- +

1

-

- +

2

2

/(n

-

5

log n

-

)

1

+

2n 5 log n 1 1

2

2

=

O(2

n3

+

0 5

,

2n / n 3 )

+

2n / n 2

+

2n /(n

-

5

log n

-

)

1

+

2

2n / n3

+

2

2

2n /(n2 (n

-

5

log n

-

))

1

+

2n / n5

2

=

2n /(n

-

5

log n

-

)

1

+

(

o 2n / n)

2

<

2n / n

1

(

+

2

(5

log n) / n)

+

o(2n / n)

2

=

2n / n

+

o(2n / n)

Insgesamt gilt die obere Schranke.

Seite 2

---