\documentclass[a4,landscape,twocolumn]{article}

\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage{amssymb}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage[margin=1cm]{geometry}

\setlength{\columnsep}{1cm}
\setlength{\columnseprule}{1pt}

\newcommand{\veta}[1]{\subsection{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\thesubsection}{\arabic{subsection}}
\newcommand{\n}[1]{\mathtt{#1}}
\newcommand{\nn}[1]{{\tt #1}}

\begin{document}
\pagestyle{empty}

\centerline{\Large Složitost II}
%\section*{Zápočtové věty}

\veta{Základní třídy a vztahy}
\begin{tabular}{llll}
	\tt LOG & $\n{DSPACE}(\log n)$ & \tt P & $\bigcup_{c\geq 0}\n{DTIME}(n^c)$\\
	\tt NLOG & $\n{NSPACE}(\log n)$ & \tt NP & $\bigcup_{c\geq 0}\n{NTIME}(n^c)$ \\
	\tt POLYLOG & $\bigcup_{c\geq 0}\n{DSPACE}(\log^c n)$ & \tt DEXT & $\bigcup_{c\geq 0}\n{DTIME}(2^{cn})$ \\
	\tt PSPACE & $\bigcup_{c\geq 0}\n{DSPACE}(n^c)$ & \tt NEXT & $\bigcup_{c\geq 0}\n{NTIME}(2^{cn})$\\
	\tt NPSPACE & $\bigcup_{c\geq 0}\n{NSPACE}(n^c)$ & \tt EXPTIME & $\bigcup_{c\geq 0}\n{DTIME}(2^{n^c})$\\
	\tt EXPSPACE & $\bigcup_{c\geq 0}\n{DSPACE}(2^{cn})$ & \tt NEXPTIME & $\bigcup_{c\geq 0}\n{NTIME}(2^{n^c})$\\
\end{tabular}
\begin{enumerate}
	\item $\n{NLOG} \subseteq \n{P} \subseteq \n{NP} \subseteq \n{PSPACE} = \n{NPSPACE} \subseteq \n{EXPTIME}$
	\item $\n{NLOG} \subset \n{PSPACE} \subset \n{EXPSPACE}$
	\item $\n{P} \subset \n{DEXT} \subset \n{EXPTIME}$
\end{enumerate}

\veta{O lineární prostorové kompresi}
Nechť je jazyk $L$ přijímán DTS $M$ s prostorovou složitostí $S(n)$. Potom 
$\forall r\in\N^+$ existuje DTS $M'$, který má prostorovou složitost $S(n)/r$ a 
přijímá $L$ (a zachovává počet pásek).

\veta{O lineárním zrychlení}
\begin{enumerate}
	\item Nechť je jazyk $L$ přijímán DTS $M$, který má časovou složitost $T(n)$ 
	a nechť $\inf_{n\to\infty} {T(n) \over n} = \infty$, potom $\forall c > 0$ 
	existuje DTS $M'$, který má časovou složitost $cT(n)$ a přijímá jazyk $L$.
	\item Nechť je jazyk $L$ přijímán DTS $M$, který má časovou složitost 
	$T(n)=cn$, kde $c>1$. Potom $\forall \epsilon > 0$ existuje DTS $M'$, který 
	má časovou složitost $(1+\epsilon)n$ a přijímá jazyk $L$.
\end{enumerate}
Neboli:
\begin{enumerate}
	\item $\inf_{n\to\infty} {T(n) \over n} = \infty \quad \Rightarrow \quad 
	\forall c>0 \quad \n{DTIME}(T(n)) = \n{DTIME}(cT(n))$
	\item $T(n) = cn, c > 1 \quad \Rightarrow \quad \n{DTIME}(T(n)) = 
	\n{DTIME}((1+\epsilon)n)$
\end{enumerate}
A úplně stejně pro nedeterministické.

\veta{O deterministické prostorové hierarchii}
Nechť $S_1,S_2: \N \to \N$ jsou funkce takové, že $S_1 \in o(S_2)$, $S_2$ je 
prostorově konstruovatelná a $S_1(n) \geq \log_2 n$. Potom existuje jazyk $L$, 
pro který platí:
$$
	L \in \n{DSPACE}(S_2(n)) \setminus \n{DSPACE}(S_1(n))
$$

\veta{O deterministické časové hierarchii}
Nechť $T_1,T_2: \N \to \N$ jsou funkce takové, že $T_1 \log T_1 \in o(T_2)$ a 
$T_2$ je časově konstruovatelná. Potom existuje jazyk $L$, pro který platí:
$$
	L \in \n{DTIME}(T_2(n)) \setminus \n{DTIME}(T_1(n))
$$

\veta{O vztazích}
Nechť $f: \N \to \N$ je funkce. Potom platí:
\begin{enumerate}
	\item $\n{NTIME}(f(n)) \subseteq \n{DSPACE}(f(n))$
	\item $L\in \n{NSPACE}(f(n)), f(n) \geq \log_2 n \quad \Rightarrow \exists c_L: 
	L\in \n{DTIME}(c_L^{f(n)})$
\end{enumerate}

\veta{Savičova}
Nechť $S: \N \to \N$ je prostorově konstruovatelná funkce taková, že $S(n) \geq 
\log_2 n$. Potom:
$$
	\n{NSPACE}(S(n)) \subseteq \n{DSPACE}(S^2(n))
$$

\veta{Translační}
Nechť $S_1, S_2, f$ jsou prostorově konstruovatelné funkce taková, že $f(n), 
S_2(n) \geq n$. Potom:
\begin{align*}
	& \n{NSPACE}(S_1(n)) \subseteq \n{NSPACE}(S_2(n)) \\
	\Rightarrow \quad& \n{NSPACE}(S_1(f(n))) \subseteq \n{NSPACE}(S_2(f(n)))
\end{align*}
{\it A podobně pro \nn{DSPACE}, \nn{DTIME} a \nn{NTIME}.}

\veta{O nedeterministické prostorové hierarchii (omezená verze pro polynomy)}
Nechť $\epsilon > 0, r \geq 1$. Potom existuje jazyk $L$, pro který platí:
$$
	L \in \n{NSPACE}(n^{r+\epsilon})\setminus \n{NSPACE}(n^r)
$$
	
\end{document}