\documentclass[a4paper,twoside]{article}
\usepackage[czech]{babel}
\usepackage[cp1250]{inputenc}
\usepackage{a4wide}
% umoznuje nastavit margins
\usepackage[hmargin=1.5cm,vmargin=2cm]{geometry}
% for multicolumn environmnet
\usepackage{multicol}
% compressed versions of listings, e.g. begin{itemize*} instead of \begin{itemize}
\usepackage{mdwlist}
% this changes labeling of second level lists
\renewcommand{\labelenumii}{\arabic{enumii}. }
%Veci pro matiku
\usepackage{amsmath, amsthm, amssymb}
%Vkladani obrazku atd.
\usepackage{graphicx}
%Vypisy pseudokodu
\usepackage{algorithmic}
\providecommand{\problem[1]}{\textit{\MakeUppercase{#1}}}
\providecommand{\OO}[1]{\operatorname{O}\bigl(#1\bigr)}
\renewcommand{\labelenumi}{(\alph{enumi})}
\author{Štěpán~Šindelář}
\title{Advanced Computational Complexity Assignment}
\begin{document}
\large
\textbf{
Advanced Computational Complexity Assignment -- Stepan Sindelar}
\normalsize
\paragraph{Questions to ask the lecturer}
\begin{itemize*}
\item are lengths of paths measured in number of edges?
\item do I have to explain details such as, how to
compare two numbers in L space, or how to check
that a number is odd.
\end{itemize*}
\paragraph{Question 1}
\begin{enumerate}
\item
Our proof is divided into these steps:
\begin{itemize}
\item we show that mapping to an edge is equivalent to finding 2-coloring,
\item we show that a graph is 2-colourable if and only if it does no have any cycle of odd length,
\item we provide a polynomial algorithm to detect an odd cycle in a graph.
\end{itemize}
\item From (a) we know that mapping to an edge is equivalent to finding 2-coloring
which is equivalent to showing that the graph does not have any odd length cycle.
Because $NL = coNL$ (shown in lectures), we can show that the problem of
recognizing the complement language is in $NL$ and we get that the
original problem is also in $NL$.
The complement language encodes all the graphs that do not map to an edge
that is all the graphs that have an odd cycle.
In the following paragraph, we describe an $NL$ algorithm to find an
odd cycle in a graph.
Our algorithm is similar to algorithm for \problem{REACHABILITY} from lectures.
We nondeterministically guess a vertex that is a part of the odd cycle.
Then we nondeterministically guess the path through the cycle back to
the original vertex and during this we count number of steps.
If we reach the original vertex, we check the counter to see if the
cycle is odd length, if so, we \textbf{accept}, otherwise we \textbf{reject}.
If we have not reached the original vertex and
the number of steps exceeds the number of edges in the graph,
we \textbf{reject}.
\subparagraph*{Correctness of the algorithm}
\begin{itemize}
\item All the branches of a computation of our algorithm eventually terminate
\begin{itemize*}
\item the counter is incremented in every step, so if a
computation branch is following a path that is not a cycle,
then it still terminates after $m$ steps.
\item if a computation branch follows a path that is cycle,
it terminates after it reaches the original vertex.
\end{itemize*}
\item Observation: if there is an odd length cycle, then there is
a computation path that \textbf{accepts}.
\item If there is not an odd length cycle in the graph,
there cannot be a computation path that \textbf{accepts},
because there is no odd length path from a vertex back to
itself and so we can never reach a state when we come back to the
original vertex and the counter is odd.
\end{itemize}
\subparagraph*{Space complexity.} We only need one counter and a
constant space to compare the counter with the number of edges.
\subparagraph*{Correctness of the algorithm}
\item
\problem{MTT} is in $NP$, because the mapping itself can be
used as an certificate. We then take each edge of the original
graph and check that the mapping of its endpoints conforms to
the definition, which can be done in linear time.
Similarly to (a) we show that \problem{MTT} is equivalent to
finding 3-coloring, which was shown to be $NP$ complete problem
at the lecture.
\item I am stuck on this one.
\end{enumerate}
\paragraph{Question 2}
\begin{enumerate}
\item The problem of finding the shortes path can be solved with
Breadth-first search \cite{algorithms}, which runs in linear time.
\item
To show that \problem{short path} is in $NL$, we
describe an $NL$ algorithm which is based upon
the algorithm for \problem{REACHABILITY} from lectures.
We perform the algorithm for \problem{REACHABILITY}, but we maintain a
counter, which is initialized to 0 and after each step incremented.
If we reach the target vertex, we \textbf{accept}.
If the counter is equal to $k$, but we have not reached
the target vertex, we \textbf{reject}.
The described algorithm solves the problem and apart from the space
requirements of \problem{reachability}, we only need
a space for the counter.
To show the $NL$ completeness of \problem{short path}.
We reduce \problem{reachability},
which is known to be $NL$ complete problem,
to \problem{short path}.
TODO: the reduction must be NL style reduction mate!
Basically, shortest path with $k=n$ works.
\item
\problem{long path} is in $NP$, because we can use the path itself
as an certificate. To check whether a path is valid and wherther
it has at least the required length has linear time complexity.
To show that \problem{long path} is $NP$ complete, we use
reduction from \problem{hamiltonian cycle}, which was shown to be
$NP$ complete at lectures.
For an input graph $G$ we create $G'$, which contains all the
vertices and all the edges of $G$ plus two new vertices $v$ and $u$.
In addition, we choose an arbitrary vertex $w$ from $G$ and in $G'$ we
introduce new edge $\{w, u\}$ and new edge $\{q_i, v\}$ for every
neighbour $q_i$ of $w$ in $G$. This conversion can be done in polynomial time.
Now, we use \problem{long path} to find a
long path from $u$ to $v$, and we want this path to be at least $n+1$
long, where $n$ is the number of vertices in $G$.
\subparagraph*{Lemma} If there is a hamiltonian cycle in $G$,
then there is a path from $u$ to $v$ with length $n+1$ in $G'$.
The hamiltonian cycle $h_1, h_2, \dots, h_n$ in $G$ must go through
vertex $w$, so WLOG let us say that $h_1 = w$, therefore $h_n$ must
be an neighbour of $w$ (because it is cycle) and we know that $G'$
contains edge $\{h_n, v\}$.
Then path $u, w = h_1, h_2, \dots, h_n, v$ has length $n+1$.
\subparagraph*{Lemma} If there is a path from $u$ to $v$ with length
$n+1$ in $G'$, then there is a hamiltonian cycle in $G$.
It must be a simple path of length $n+1$, so it must visit $n+2$ vertices
that is all the vertices in $G'$. Since we start from $u$, the only
edge we can start with is $\{u, w\}$. Because we cannot repeat any
vertex in the path and because we need the path to be $n+1$ long,
we cannot use any edge with $v$ as one of its
endpoints until we visit all the vertices from $G$. Therefore the
path must look like $u, w = h_1, h_2, \dots, h_n, v$ where $h_1, \dots, h_n$
are all the vertices from $G$. $h_n$ must be a neighbour of $w = h_1$, because
$v$ is connected only to neighbours of $w$. Hence $h_1, \dots, h_n$
form a hamiltonian cycle in $G$.
\end{enumerate}
\bibliographystyle{ieeetr}
\bibliography{complex-ssindelar}
\end{document}
\section{Výpis pseudokódu}
\subparagraph{}
\begin{algorithmic}[1]
\STATE $P_{max} \gets$ délka nejdelšího slova.
\STATE $L_{i} \gets$ slova délky $i$ pomocí bucket sortu.
\STATE $S = \emptyset$ bude výsledný setříděný seznam.
\FOR{$i = P_{max}$ to $1$}
\STATE $R_c \gets$ slova z $P_i$ se znakem $c$ na $i$-té pozici odzadu.
\STATE $R_c \gets$ slova ze $S$ se znakem $c$ na $i$-té pozici odzadu.
\STATE $S = \emptyset$
\FOR{$\forall{c}$ podle uspořádání}
\STATE do $S$ přidej prvky $R_c$
\ENDFOR
\ENDFOR
\STATE označ $S$ za výsledek.
\end{algorithmic}