\documentclass{slides}
\usepackage{amsmath,amssymb}
\begin{document}
\slide
Offensichtliche obere Schranke \\
f\"ur 
die Komplexit\"at aller $n$-stelligen
Booleschen Funktionen
\[
f : \mathcal{B}^n \rightarrow \mathcal{B}
\]
basierend auf DNF bzw. KNF:

Bereitstellen aller Minterme bzw. Maxterme (vgl. decode)
\begin{eqnarray*}
C_{\Omega_0} &\leq & 2^{n-1} + (2n-2) 2^{n/2} \\
D_{\Omega_0} &\leq &\lceil \log_2 n\rceil +1
\end{eqnarray*}

Maximal $2^{n-1}-1$ Disjunktionen bzw. Konjunktionen
mit Tiefe $\leq \lceil \log_2 2^{n-1} \rceil = n-1$
\begin{eqnarray*}
C_{\Omega_0}(f) &\leq & 2^{n} + (2n-2) 2^{n/2} \\
D_{\Omega_0}(f) &\leq & n + \lceil \log_2 n\rceil
\end{eqnarray*}


\slide
Eine untere Schranke f\"ur die Komplexit\"at\\
(Schaltkreisgr\"osse)
``der meisten'' BF

\bigskip

Sei $0 < \epsilon < 1$. F\"ur hinreichend grosses $n$:
\[
n \geq 2 \frac{1-\epsilon}{\epsilon} 
\log_2 (3 \epsilon)^2(1 - \epsilon/2))
\]
ist der Anteil der Booleschen Funktionen\\ 
$f : \mathcal{B}^n \rightarrow \mathcal{B}$
mit sehr hoher Komplexit\"at:
\[
C_{\Omega_0}(f) \geq
\frac{2^n}{n}(1 - \epsilon) - 2 n^2
\]
an der Menge aller $n$-stelligen 
BF sehr hoch:
\[
\geq
1 - \frac{1}{2^{(\epsilon/2)2^n}}
\]
\textit{
``Es gibt (verglichen mit der Gesamtzahl aller BF) 
relativ wenige kleine Schaltkreise, \\
deshalb sind die meisten BF nur
mit Schaltkreisen sehr grosser Komplexit\"at
zu realisieren''}

\slide


Beweisskizze: mit $g$ Gattern $\in \Omega_0 = \{\neg,\vee,\wedge\}$
lassen sich
\[
\leq 3^g (g+n)^{2g}
\]
verschieden LSK mit $n$ inputs konstruieren.

Dadurch weren alle $n$-stelligen BF $f$ mit\\
$C_{\Omega_0}(f) \leq g$ dargestellt.

Der Anteil dieser BF an der Menge aller $n$-stelligen BF
ist also
\[
\leq \frac{3^g (g+n)^{2g}}{2^{2^n}}
\]

W\"ahle nun $g = 2^n/(a \cdot n)$ mit $a > 2$. 
Dann ist dieser relative Anteil
$\leq b^{2^n}$ mit
\[
b = \frac{\left[3 \left(\frac{2^n}{an}+n\right)^2\right]^{1/an}}{2}
\]
F\"ur hinreichend grosses $n$ ist dies
\[
<  \frac{1}{2^{1 - (2/a)}} < 1
\]

\slide
Eine untere Schranke f\"ur die Komplexit\"at\\
(Schaltkreistiefe)
``der meisten'' BF

\bigskip

Sei $0 < \delta < 1$. F\"ur $n \geq 5$
ist der Anteil der BF\\ 
$f : \mathcal{B}^n \rightarrow \mathcal{B}$
mit sehr grosser Tiefe:
\[
D_{\Omega_0}(f) \geq
n - \log \log n - O(1)
\]
an der Menge aller $n$-stelligen 
BF sehr hoch:
\[
\geq
1 -  \frac{1}{2^{\delta 2^n}}
\]
\textit{
``Es gibt (verglichen mit der Gesamtzahl aller BF)
relativ wenige flache Schaltkreise\\
 (genauer: bin\"are B\"aume
geringer Tiefe), \\
deshalb sind die meisten BF nur mit Schaltkreisen
sehr grosser Tiefe zu realisieren''}


\slide
Beweisskizze: Es sei\\
$C(d)$ = Anzahl nicht-orientierter bin\"arer B\"aume mit Tiefe $\leq d$\\
$T(d)$ = Anzahl nicht-orientierter bin\"arer B\"aume mit Tiefe $= d$

Aus den offensichtlichen Beziehungen
\begin{eqnarray*}
C(d) & = & C(d-1) + T(d) \\
T(d+1) & = & T(d)C(d\!-\!1) + 
\frac{T(d)(T(d)\!-\!1)}{2} + T(d)
\end{eqnarray*}
erh\"alt man eine Rekursionsgleichung f\"ur $T(d)$:
\[
\frac{T(d+2)}{T(d+1)}
=
\frac{T(d+1)}{T(d)} + \frac{T(d+1)+T(d)}{2}
\]
die zu der Absch\"atzung
\[
T(d) \leq T(d-1)^2~~~\text{f\"ur}~d \geq 5
\]
und schliesslich zu
\[
T(d) \leq (56)^{2^{d-4}}~~~\text{f\"ur}~d \geq 5
\]
f\"uhrt. 

Die Anzahl $N(d)$ der ``tree circuits''
\"uber $\Omega_0$ mit Tiefe $d$ und $n$ inputs kann also
abgesch\"atzt werden durch
\[
N(d) \leq T(d) \cdot 3^{2^d} \cdot (n+2)^{2^d} \leq c^{2^d}
\]
(f\"ur $d \geq 4$), wobei $c \leq 4 (n+2)$.

Die Bedingung (f\"ur ``tree circuits'' mit Tiefe $\leq d$)
\[
c^{2^{d+1}} \leq 2^{2^n(1 - \delta)}
\]
kann durch zweimaliges Logarithmieren in eine
Bedingung f\"ur $d$ \"ubersetzt werden.

\slide

Eine obere Schranke f\"ur die Komplexit\"at\\
 (Schaltkreisgr\"osse)
aller BF\\
(Konstruktion von Lupanov)

\bigskip

Sei $\epsilon > 0$. F\"ur hinreichend grosses $n$\\
(von $\epsilon$ abh\"angig) gilt
\[
C_{\Omega_0} (f) \leq
\frac{2^n}{n}(1 + \epsilon)
\]
f\"ur \textit{jede} $n$-stellige BF

\textit{\textit{Jede}
$n$-stellige BF kann durch einen Schaltkreis dargestellt werden,
dessen Gr\"osse relativ ``nahe'' an der unteren Schranke liegt,
die f\"ur ``die meisten'' BF zutrifft.}
\end{document}