\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}
\usepackage{eurosym}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 11}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\eur}{\mbox{\euro}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
\subsubsection*{(a)}
Wir definieren $f$ und $g$ wie folgt:
\begin{align*}
	f(n) &= \begin{cases}n^3 & \mbox{ falls $n$ ungerade} \\ n & \mbox{ falls $n$ gerade} \end{cases} \\[0.5cm]
	g(n) &= \begin{cases}n^3 & \mbox{ falls $n$ Primzahl} \\ n^2 & \mbox{ sonst} \end{cases}
\end{align*}
\begin{itemize}
	\item Behauptung: $f \not\in \OnotO(g)$ \\
		Beweis: \\
		Angenommen, es gäbe ein $n_0 \in \SetN$ und $c > 0$ mit der Eigenschaft, dass $f(n) \leq c \cdot g(n)$ für alle $n \geq n_0$. Dann setzen wir $n'$ auf eine ungerade Zahl größer als $c$, die keine Primzahl ist und erhalten $f(n') = n'^3 > c \cdot n^2 = c \cdot g(n)$, was ein Widerspruch zur Annahme ist.
	\item Behauptung: $g \not\in \OnotO(f)$ \\
		Beweis: \\
		Angenommen, es gäbe ein $n_0 \in \SetN$ und $c > 0$ mit der Eigenschaft, dass $g(n) \leq c \cdot f(n)$ für alle $n \geq n_0$. Dann setzen wir $n'$ auf eine gerade Zahl größer als $c$ und erhalten $g(n') = n'^2 > c \cdot n = c \cdot f(n)$, was ein Widerspruch zur Annahme ist.
\end{itemize}

\subsubsection*{(b)}
Definiere die Funktionen
$$gerade(n) = \begin{cases} 1 & \mbox{ falls $n$ gerade} \\ 0 & \mbox{ sonst} \end{cases}$$
und $ungerade(n)$ analog. \\
Betrachte die Funktionen $f(n) = n^{n + gerade(n)}$ und $g(n) = n^{n + ungerade(n)}$. Es gilt offensichtlich $f(n) \neq g(n)$ für $n \geq 2$ und $f(n),g(n) \in \{n^n, n^{n+1}\}$. Genauer gesagt: Für $n \geq 2$ und $n$ gerade, ist $f(n) = n \cdot g(n)$ und für $n$ ungerade ist $g(n) = n \cdot f(n)$. \\
Beide Funktionen sind streng monoton steigend. \\
Dies wird für $f(n)$ gezeigt. Es ist
\begin{align*}
f(n + 1) &= (n + 1)^{n + 1 + gerade(n + 1)} \\
&\geq (n + 1)^{n + 1} \\
&= (n + 1)^n \cdot (n + 1)^1 \\
&> n^n \cdot n^1 \\
&> n^n \cdot n^{gerade(n)} \\
&= f(n)
\end{align*}
Es gilt $f \not\in \OnotO(g)$ und $g \not\in \OnotO(f)$. Die erste Aussage wird gezeigt; die zweite folgt analog. \\
Zu zeigen ist: $\forall c > 0: \forall n_0: \exists n \geq n_0: f(n) > c \cdot g(n)$. Bei gegebenen $c$ und $n_0$ wählt man $n$ als gerade Zahl größer als $\max\{2,c,n_0\}$. Dann gilt $f(n) = n \cdot g(n) > c \cdot g(n)$.

\section*{Aufgabe 2}
Sei $g(n) = b^{f(n)}$, wobei $b$ eine Konstante, die abhängig von $L$ ist. Dann erfüllt $g$ die geforderten Eigenschaften. \\
\textbf{Beweis:}
\begin{align*}
	L \in \mathsf{NTIME}(f(n)) &\overset{\mbox{\tiny Lemma B (ii)}}{\Longrightarrow} L \in \mathsf{DTIME}(b^{f(n)}) \\
	&\overset{\mbox{\tiny Lemma D (i)}}{\Longrightarrow} \overline{L} \in \mathsf{DTIME}(b^{f(n)}) \\
	&\overset{\mbox{\tiny Lemma B (i)}}{\Longrightarrow} \overline{L} \in \mathsf{NTIME}(b^{f(n)})
\end{align*}

\end{document}