fmi-ss12-b1_local.tex

%\usepackage{graphicx}
%\usepackage{typearea}
%\usepackage{multicol}
%\usepackage{amsfonts}
%\usepackage[nounderscore]{syntax}
%\usepackage{paralist}
%\usepackage{tikz}
%\usetikzlibrary{positioning}
%\usepackage{url}
%\usepackage{xspace}
%\usepackage{bbm}
%\usepackage{listings}
%%\usepackage{MnSymbol}
%%\usepackage[ruled]{algorithm2e}
%\def\NN{{\ensuremath{\mathbbm{N}_0\xspace}}}
%\usepackage{wrapfig}
%\usepackage{graphicx}
%\usetikzlibrary{arrows,automata}
%\setlength{\textheight}{25cm}
%%% useful macros for Turing machines:
%\usepackage{algpseudocode}


\documentclass[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage[amsmath,amsthm]{ntheorem}
\usepackage[pagebackref=true,colorlinks=true,linkcolor=blue]{hyperref}
\usepackage{lastpage}
\usepackage{epsfig}
\usepackage{float}
\usepackage{xspace}
\usepackage{paralist}
\usepackage{enumerate}
\usepackage[boxed]{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2606}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{LastRevised=Monday, April 02, 2012 02:58:56}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}

   \textwidth      15cm
   \textheight     23cm
   \oddsidemargin 0.5cm
   \topmargin    -0.5cm
   \evensidemargin\oddsidemargin
\newcommand{\nop}[1]{}
   \pagestyle{plain}
   \bibliographystyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{exercise}[theorem]{Exercise}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\LR}{\Leftrightarrow}
  \renewcommand{\phi}{\varphi}
  \renewcommand{\theta}{\vartheta}
\newcommand{\ccfont}[1]{\protect\mathsf{#1}}
\newcommand{\NP}{\ccfont{NP}}
\newcommand{\NN}{\textbf{N}}
\newcommand{\IN}{\textbf{Z}}
\newcommand{\bigO}{\mathrm{O}}
\newcommand{\bigOmega}{\Omega}
\newcommand{\bigTheta}{\Theta}
\newcommand{\REACHABILITY}{\mbox{\bf REACHABILITY}}
\newcommand{\MAXFLOW}{\mbox{\bf MAX FLOW}}
\newcommand{\MAXFLOWD}{\mbox{\bf MAX FLOW(D)}}
\newcommand{\MAXFLOWSUB}{\mbox{\bf MAX FLOW SUBOPTIMAL}}
\newcommand{\MATCHING}{\mbox{\bf BIPARTITE MATCHING}}
\newcommand{\TSP}{\mbox{\bf TSP}}
\newcommand{\TSPD}{\mbox{\bf TSP(D)}}
\newcommand{\ThreeCol}{\mbox{\bf 3-COLORABILITY}}
\newcommand{\TwoCol}{\mbox{\bf 2-COLORABILITY}}
\newcommand{\kCol}{\mbox{\bf k-COLORABILITY}}
\newcommand{\HamPath}{\mbox{\bf HAMILTON-PATH}}
\newcommand{\HamCycle}{\mbox{\bf HAMILTON-CYCLE}}
\newcommand{\ONESAT}{\mbox{\bf 1-IN-3-SAT}}
\newcommand{\MONONESAT}{\mbox{\bf MONOTONE 1-IN-3-SAT}}
\newcommand{\kSAT}{\mbox{\bf k-SAT}}
\newcommand{\NAESAT}{\mbox{\bf NAESAT}}
\newcommand{\CLIQUE}{\textbf{CLIQUE}\xspace}
\newcommand{\VC}{\textbf{VERTEX COVER}\xspace}
\renewcommand{\labelenumi}{(\alph{enumi})}
\newcommand{\blank}{\sqcup}
\newcommand{\ssym}{\triangleright}
\newcommand{\esym}{\triangleleft}
\newcommand{\halt}{\mbox{h}}
\newcommand{\yess}{\mbox{``yes''}}
\newcommand{\nos}{\mbox{``no''}}
\newcommand{\lmove}{\leftarrow}
\newcommand{\rmove}{\rightarrow}
\newcommand{\stay}{-}
\newcommand{\diverge}{\nearrow}
\newcommand{\yields}[1]{\stackrel{#1}{\rightarrow}}
\newcommand{\HALTING}{\mbox{\bf HALTING}}
\newcommand{\true}{{\it true}}
\newcommand{\false}{{\it false}}
\newcommand{\samplesolution}[1]{\noindent {\bf Sample solution.}  #1}
\input{tcilatex}

\begin{document}

\title{Formale Methoden der Informatik \\
Block 1: Computability and Complexity }
\author{Exercises 1-10}
\date{SS 2012}
\maketitle

\begin{exercise}
Consider the problem \textbf{PROCEDURE NEG-ASSIGNMENT}, which is defined as
follows:

\fbox{ 
\begin{minipage}[c]{.9\linewidth}
        \textbf{PROCEDURE NEG-ASSIGNMENT}

        \medskip INSTANCE: A triple $(\Pi,I, k)$, where (i) $\Pi$ is a
        program that takes one string as input and outputs true or false, (ii) $I$ is a
        string, and (iii) $k$ is an integer variable used in program $\Pi$.     \\
        QUESTION: Does variable $k$ ever get assigned a negative value when the program $\Pi$ is executed with input $I$?

        
      \end{minipage}
    }

Prove that \textbf{NEG-ASSIGNMENT} is undecidable. Prove the undecidability
by providing a reduction from the \textbf{HALTING} problem to \textbf{%
NEG-ASSIGNMENT}, and arguing that your reduction is correct.
\end{exercise}

\textbf{Proof}: Reduction from \textsc{Halting} problem to \textsc{%
Neg-Assignment}.

Let $(\Pi ,I)$ be an arbitrary instance of \textsc{Halting}, i.e. $\Pi $ \
is a program that takes an input. Based on this, we have to construct an
instance $(\Pi ^{\prime },I^{\prime },k)$ for \textsc{Neg-Assignment} by
setting $I^{\prime }=I$ and setting initially $k\geq 0$. Then $\Pi ^{\prime
} $ is defined as follows:

%TCIMACRO{%
%\TeXButton{Procedure}{\begin{center}
%\fbox{
%\begin{minipage}[c]{.9\linewidth}
%\small
%boolean $\Pi'$(String $S$) $\{$\\
%int $k := 0$;\\
%call $\Pi(S)$;\\
%$k := -1$;\\
%return true;\\
%$\}$\\
%
%\end{minipage}
%}
%\end{center}}}%
%BeginExpansion
\begin{center}
\fbox{
\begin{minipage}[c]{.9\linewidth}
\small
boolean $\Pi'$(String $S$) $\{$\\
int $k := 0$;\\
call $\Pi(S)$;\\
$k := -1$;\\
return true;\\
$\}$\\

\end{minipage}
}
\end{center}%
%EndExpansion

Let $x=(\Pi ,I)$ be an instance of \textsc{Halting} and $R(x)=(\Pi ^{\prime
},I^{\prime },k)$ the resulting instance from the reduction. Then, we have
to show that $x$ is reducible to $R(x)$ by following equivalence relation:%
\begin{eqnarray*}
&&(\Pi ,I)\text{ is a positive instance of \textsc{Halting}}%
\quad\Leftrightarrow\quad (\Pi ^{\prime },I^{\prime },k)\text{ is apositive
instance} \\
&&\text{of the procedure \textsc{Neg-Assignment}.}
\end{eqnarray*}

(i.e. $\Pi $ halts on $I$ and assigns to $k$ a negative integer value$\quad
\Leftrightarrow\quad \Pi^{\prime }$ returns \textit{true}.)

$\Rightarrow :$ Suppose that $\left( \Pi ,I\right) $ is a positive instance
of \textsc{Halting}, i.e. $\Pi $ terminates on $I$.

Then by construction of $(\Pi ^{\prime },I^{\prime },k)$, the call of $\Pi
(I^{\prime })$ in program $\Pi ^{\prime }$ terminates since $I^{\prime }=I$.
Hence, $\Pi ^{\prime }$ halts on input $I^{\prime }$, assignes $k:=-1$ and
returns \textit{true} respectively.

Thus, $(\Pi ^{\prime },I^{\prime },k)$ is a positive instance of \textsc{%
Neg-Assignment}.

$\Leftarrow :$ Suppose that $\left( \Pi ^{\prime },I^{\prime },k\right) $ is
a positive instance of \textsc{Neg-Assignment}, i.e. $\Pi ^{\prime }$
returns \textit{true} after assigning a negative value to $k$. Since $\Pi
^{\prime }$ involves the call of $\Pi (I^{\prime })$ with $I^{\prime }=I$, $%
\Pi $ terminates on $I$ and $k$ will be set to $-1$. Hence, $(\Pi ,I)$ is a
positive instance of \textsc{Halting}.

\bigskip

\begin{exercise}
Prove that the problem \textbf{NEG-ASSIGNMENT} from Exercise 1 is
semi-decidable. To this end, provide a semi-decision procedure and justify
your solution. Additionally, show that the co-problem of \textbf{%
NEG-ASSIGNMENT} is not semi-decidable.
\end{exercise}

\textbf{Proof:}

To show that \textsc{Neg-Assignment} is semi-decideable, we have to build a
procedure $\Pi ^{\prime }$ that satisfies following conditions:

\begin{itemize}
\item $\Pi ^{\prime }$ takes as input an instance of \textsc{Neg-Assignment}%
, i.e. $\left( \Pi ,I,k\right) $,

\item $\Pi ^{\prime }$ simulates a run of $\Pi $ on $I$ and assigns internal
the variable $k$ an integer value,

\item if the simulation reaches the assignment where $k$ will be set to a
negative value, then $\Pi ^{\prime }$ returns \textit{true},

\item if the simulation halts before reaching the negative value assignment
of $k$ (i.e. $k\geq 0$), then $\Pi ^{\prime }$ returns \textit{false},

\item if the simulation of $\Pi $ on $I$ does not terminate, then $\Pi
^{\prime }$ cannot return any value and thus, $k$ will never set to a
negative value.
\end{itemize}

\bigskip Hence, the termination of the program $\Pi $ is only guaranteed on 
\textit{positive instances}.

Then $\Pi ^{\prime }$ can be argued as a semi-decision procedure for \textsc{%
Neg-Assignment} as follows:

Let $x=\left( \Pi ,I,k\right) $ be an arbitrary instance of \textsc{%
Neg-Assignment}, then

\begin{description}
\item[\normalfont\slshape Case 1:] Suppose that $x$ is a positive\ instance
(a "yes"-instance), s.t. the program $\Pi $ on input $I$ terminates and $k$
will be assinged by a negative value. Then by construction of $\Pi ^{\prime
} $, the simulation in $\Pi ^{\prime }$ on $I^{\prime }=I$ will encounter an
assignment to $k$, where $k$ get a negative value (i.e. $k:=-1$) and thus, $%
\Pi ^{\prime }$ returns \textit{true}.

\item[\normalfont\slshape Case 2:] 

\item[\textit{a)}] Suppose that $x$ is a "no"-instance, i.e. the program $%
\Pi $ on input $I$ halts without reaching the negative value assignment of $%
k $. Then by construction of $\Pi ^{\prime }$, the simulation in $\Pi
^{\prime }$ on input $I^{\prime }=I$ is not able to change the initial value
assignment of $k$, with $k\geq 0$, to a negative value. Hence, $\Pi ^{\prime
}$ returns \textit{false}.

\item[\textit{b)}] Suppose that $x$ is negative instance and $\Pi $ does not
halt on input $I$, i.e. $\Pi $ does not terminate (loops forever). Then the
simulation in $\Pi ^{\prime }$ on $I^{\prime }=I$ will also run forever and $%
k$ will never assigned with a negative integer value. Hence, $\Pi ^{\prime }$
will run forever on the negative instance $(\Pi ,I,k)$ and will never return
any output.
\end{description}

Thus, both behaviors of the negative cases describes a correct behavior for
a semi-decision procedure.

\medskip

Co-problem of \textsc{Neg-Assignment}:

\bigskip

\begin{exercise}
Give a formal proof that \textbf{SUBSET SUM} is in $\mathsf{NP}$,
i.e.\thinspace\ define a certificate relation and discuss that it is
polynomially balanced and polynomial-time decidable.

\smallskip

\noindent In the \textbf{SUBSET SUM} problem we are given a finite set of
integer numbers $S=\{a_{1},a_{2},\ldots ,a_{n}\}$ and an integer number $t$.
We ask whether there is a subset $S^{\prime }\subseteq S$ whose elements sum
is equal to $t$?
\end{exercise}

\textbf{Proof:}

To prove that \textsc{Subset-Sum} $\in $ NP, we have to define a
polynomially balanced and polynomially decidable certificate relation for 
\textsc{Subset-Sum}:

Let $S=\{a_{1},\ldots ,a_{n}\}$ be an arbitrary finite set of integer
numbers with $n\geq 1$ and let $t$ $\in \mathbb{N}$, s.t. $t\geq 1$.

Then the certificate relation for \textsc{Subset-Sum} is defined as follows:

\begin{equation*}
R_{S}=\{\langle S,t\rangle \mid \exists \,S^{\prime }\subseteq S\text{ s.t. }%
t=\tsum\limits_{a\in S^{\prime }}a\text{ and }t\geq 1\}.
\end{equation*}

We argue that $R_{S}$ is indeed a certificate relation for \textsc{Subset-Sum%
}, since following holds:

\begin{gather*}
S\text{ is a positive instance of \textsc{Subset-Sum}}\quad \Leftrightarrow
\\
\exists \text{ a certificate subset }S^{\prime }\subseteq S\text{ of
non-negative integers, s.t. }\tsum\limits_{a\in S^{\prime }}a=t\quad
\Leftrightarrow \\
\exists \,t\in \mathbb{N}^{+}\text{, s.t. }\langle S,t\rangle \in R_{S}\text{%
.}
\end{gather*}

\begin{itemize}
\item $R_{s}$ is \textit{polynomial balanced} since every subset $S^{\prime
}\subseteq S$ of integer values can be represented in linear space (array)
and the sum of elements is $t$, which uses only constant space.

\item $R_{s}$ is \textit{polynomial-time decidable} since the sum of all
elements of $S^{\prime }\subseteq S$ needs linear time. Hence, $S^{\prime }$
can be finished at most in polynomial time.
\end{itemize}

\bigskip

\begin{exercise}
\label{ex:partition} Formally prove that \textbf{PARTITION} is $\mathsf{NP}$%
-complete. For this you may use the fact that \textbf{SUBSET SUM} is $%
\mathsf{NP}$-complete.

\smallskip \noindent In the \textbf{PARTITION} problem we are given a finite
set of integers $S=\{a_{1},a_{2},\ldots ,a_{n}\}$. We ask whether the set $S$
can be partitioned into two sets $S_{1},S_{2}$ such that the sum of the
numbers in $S1$ equals the sum of the numbers in $S_{2}$?
\end{exercise}

\begin{exercise}
\label{ex:frequency} Formally prove that \textbf{FREQUENCY ASSIGNMENT} is $%
\mathsf{NP}$-complete. For this you may use the fact that a similar problem
used in lectures is $\mathsf{NP}$-complete.

\noindent In the \textbf{FREQUENCY ASSIGNMENT} problem we are given a set of
transmitters $T=\{t_{1},t_{2},\ldots ,t_{n}\}$, $k$ frequencies, and the
list of pairs of transmitters that interfer and therefore cannot use the
same frequency. We ask whether there is an assignment of each transmitter to
one of $k$ frequencies such that there is no interference between the
transmitters.
\end{exercise}

The NP-hardness of the \textsc{Frequency-Assignment} problem can be shown by
a reduction to $k$\textsc{-Colorability}, since $k$\textsc{-Colorability} is
in NP.

At first we have to check \ if \textsc{Frequency-Assignment} id a membership
of NP.

\begin{definition}
Let\ $G_{F}=(T,E)$ be an arbitrary undirected graph for \textsc{%
Frequency-Assignment} with $T=\{t_{1},t_{2},\ldots ,t_{n}\}$ and $E^{\prime
}=\{(t_{i},t_{j})\mid t_{i},t_{j}\in T(G_{F})$ with $i\neq j$ s.t. $t_{i}$
and $t_{j}$ are interfering each other$\}\subseteq E=\{(t_{i},t_{j})\mid
t_{i},t_{j}\in T(G_{F})$ with $i\neq j\}$. Let $F=\{f_{1},\ldots ,f_{k}\}$
be an arbitrary set of frequencies and $fr:T(G_{F})\rightarrow F$ a function
for assigning each transmitter-vertex $t\in T(G_{F})$ to a frequency $f\in F$%
.
\end{definition}

This can be done by a guess \& check procedure:\newline
\smallskip

\noindent Guess an arbitrary set of frequencies $F=\{f_{1},\ldots ,f_{k}\}$
of size $k$. Then for each transmitter-vertex $t\in T(G_{F})$, verify that $%
t $ has no adjacent verteices $u\in T(G_{F})$ with the same frequency $f\in
F $, i.e. $\forall t_{i},t_{j}\in T(G_{F})$ with $i\neq j$, s.t. $%
(t_{i},t_{j})\in E$ and $fr(t_{i})\neq fr(t_{j})$. The verification of the
edges in $G_{F}$ takes polynomial time in the size of $k=|F|$ and the number
of edges $n=|E|$ in $G_{F}$.

It remains to show that \textsc{Frequency-Assignment} is NP-hard, by
reducing \textsc{Frequency-Assignment} to $k$\textsc{-Colorability}.

Let\ $G_{F}=(T,E)$ be an arbitrary undirected graph for \textsc{%
Frequency-Assignment} (as defined above). To prove the correctness of the
reduction, we have to show that following equation holds:%
\begin{gather*}
(G_{F},k)\text{ is a positive instance of \textsc{Frequency-Assignment}}%
\quad \Leftrightarrow \\
(G_{C},k^{\prime })\text{ is a positive instance of }k\text{\textsc{%
-Colorability}.}
\end{gather*}

\textbf{Proof:}

Given an arbitrary instance $(G_{F},k)$ of \textsc{Frequency-Assignment}.
Then an instance of $(G_{C},k^{\prime })$ of $k$\textsc{-Colorability} can
be produced iff, $k=k^{\prime }$ and there exists a function $%
c:V(G_{C})\rightarrow C$, where $C=\{1,\ldots ,k^{\prime }\}$ is a set of
colors of size $k^{\prime }$.

$\Rightarrow :$ Suppose $(G_{F},k)$ is a positive instance of \textsc{%
Frequency-Assignment}. Then $\forall t_{i},t_{j}\in T(G_{F})$ with $i\neq j$%
, every edge $(t_{i},t_{j})\in E(G_{F})$, has pairwise different frequencies
such that $fr(t_{i})\neq fr(t_{j})$. We have to define an assignment
function $\mu $ such that $\mu :fr(t)\rightarrow c(v)$, for all $t\in
T(G_{F})$ and for\ all $v\in V(G_{C})$. Since $(G_{F},k)$ is a positive
instance of \textsc{Frequency-Assignment}, then there exists a corresponding
mapping $\mu $ from each node $t\in T(G_{F})$ to each node $v\in V(G_{C})$,
such that $\forall (t_{i},t_{j})\in E(G_{F}):fr(t_{i})\neq fr(t_{j})$ and

$\forall (v_{i},v_{j})\in E(G_{C}):c(v_{i})\neq c(v_{j})$ and $i\neq j$ and $%
k=k^{\prime }$. This means that both functions are behaving identical on
each graph, such that $fr=c$, i.e. there is a \textit{bijection} between the
vertex sets of $G_{F}$ and $G_{C}$. Thus, both undirected graphs $G_{F}$ and 
$G_{C}$ are \textit{isomorph}. Hence, $(G_{C},k^{\prime })$ is a positive
instance of $k$\textsc{-Colorability}$.$

$\Leftarrow :$ Suppose that $(G_{C},k^{\prime })$ is a positive instance of $%
k$\textsc{-Colorability}. Then there exists an assignment function $\mu $
(similar as above but in the other direction), such that $\mu
:c(v)\rightarrow fr(t)$ for all $v\in V(G_{C})$ and for all $t\in T(G_{F})$.
Since there exists a bijection on both vertex sets of the graphs $G_{C}$ and 
$G_{F}$, i.e. both graphs are \textit{isomorph}, $(G_{F},k)$ is also a
positive instance of \textsc{Frequency-Assignment}.

\bigskip

\begin{exercise}
\label{ex:CO-NP} Fomally prove that logical entailment is $co-\mathsf{NP}$%
-complete. The formal definition of entailment ( $\models $) is this: $%
\alpha \models \beta $ if and only if, in every truth assignment in which $%
\alpha $ is true, $\beta $ is also true.
\end{exercise}

By trying to prove that $\models $ is \textit{co-NP-complete} we whave to
show that

\begin{itemize}
\item entailment is in \textit{co-NP} \dots\ Membership (through reduction)
and

\item \textit{NP}-hardness \dots\ \textit{co-NP}-complete Problem can be
reduced to \textit{entailment}
\end{itemize}

\subsubsection{Membership}

And the counterprove for us that we have to show is that:%
\begin{equation*}
\alpha \models \beta \quad \iff \quad \models (\alpha \wedge \lnot \beta )%
\text{ is not satisfiable.}
\end{equation*}

\noindent We try to show membership through a reduction from \textit{%
entailment} the well known co-NP-complete problem: \textit{co-SAT}.\newline

\noindent Proof $\Rightarrow $:\newline
We take a look at \textbf{every truth assignments}, i.e. all interpretations 
$I$, which for \textit{entailment} means, that $\forall I$ s.t. $I(\alpha
\wedge \lnot \beta )$ isn't satisfied and therefore \textbf{also true}.

The last case - a \textbf{false} \textit{entailment} (i.e. $\alpha =true$
and $\beta =false$) followes a satisfied $\alpha \wedge \lnot \beta $ which
is \textbf{also false}.

\noindent Proof $\Leftarrow $:\newline
If $\forall I,$ $I(\alpha \wedge \lnot \beta )$ isn't satisfiable, the
entailment is \textit{true}.\newline
So in case that $\alpha \wedge \lnot \beta $ is true (s.t. $\alpha =true$
and $\beta =false$), i.e. $\models \lnot \beta $, the \textit{entailment} is
not valid and therefore it covers all of \textit{co-SAT}. Thus, \textit{%
co-SAT} is \textit{co-NP}-complete.

\subsubsection{NP-hardness}

We try to show a reduction from \textit{co-SAT} to \textit{entailment}%
\begin{equation*}
\models (\alpha \wedge \lnot \beta )\text{ is not satisfiable}\quad \iff
\quad \alpha \models \beta
\end{equation*}%
Since \textit{SAT}\ is \textit{NP}-complete and fortunately we already
proved this reduction, while showing the Membership above.\newline

\noindent This show's us, that \textit{entailment} is \textit{co-NP}-hard
and -complete.

\bigskip

\begin{exercise}
\label{ex:Colors} It is well known that the \textbf{k-COLORABILITY} problem
is $\mathsf{NP}$-complete for every $k\geq 3$. Recall that the instance of 
\textbf{k-COLORABILITY} is an undirected graph $G=(V,E)$. Suppose that we
restrict this instance of \textbf{k-COLORABILITY} to trees. Can the
restricted problem be solved with an algorithm that runs in polynomial time?
If yes, provide such an algorithm.
\end{exercise}

\noindent \textbf{Argumentation:}

The restricted problem of \textsc{Vertex k-Coloring} to trees can be solved
in polynomial time.

Let $G_{T}=(V,E)$ be an arbitrary tree with the vertex set $V=\{v_{1},\ldots
,v_{n}\}$ and a mapping $c:V(G_{T})\rightarrow \{1,,\ldots ,k\}$ such that $%
V_{i}=\{v\in V(G_{T})\mid c(v)=i\}$ and $c(u)\neq c(v)$, whenever $u,v\in V$
are adjacent $\forall (u,v)\in E(G_{T})$. Let us denote $\langle
V_{i}\rangle $ the \textit{subgraph induced by }$V_{i}$ in $G_{T}.$ (Note: $%
\langle V_{i}\rangle $ is possiblely a disconnected subgraph of $G_{T}$.)
Depending on the graph property $\Pi _{T\text{ }}$for trees, which can be
enforced on each $\langle V_{i}\rangle $, there can be defined different
coloring concepts. If each $V_{i}$ is an \textit{independent set} for $1\leq
i\leq k$, then the coloring function $c$ is a proper $k$-coloring.

Then the \textit{maximum independent set of a tree} can be found in \textit{%
linear time}, by 
\begin{inparaenum}[\itshape 1\upshape)]
\item stripping off all the end-vertices (leaf nodes),
\item adding them to the independent set,
\item deleting the newly formed end-nodes and
\item repeating from the first step until the resulting tree is empty.
\end{inparaenum}Moreover if each $V_{i}$ induces a forest (i.e. each
connected component of $V_{i}$ is a tree), then the coloring function $c$ is
called a $k$\textit{-tree coloring}. Then every graph has a proper $k$%
-coloring if the integer value $k$ is large enough. Since $G_{T}$ is an
acyclic connected graph, then every vertex $v$ is pairwise different colored
to its predecessor node $\pi (v)=u$.

Then the \textit{predecessor subgraph} of a depth-first search, denoted as $%
G_{\pi }=(V,E_{\pi })$ with $E_{\pi }=\{(\pi (v),v)\mid v\in V$ and $\pi
(v)\neq $ \textsc{Null}$\}$, forms a \textit{depth-first forest} which is
composed of serveral \textit{depth-first trees}, since the search can be
repeated from several multiple sources. The edges in $E_{\pi }$ are also
called \textit{tree edges}.

The following pseudocode (\ref{alg_k-coloring_dfs}) is a modified version of
the basic depth-first-search algorithm.

%TCIMACRO{%
%\TeXButton{DFS-Algortim for k-Coloring}{\floatname{algorithm}{Algorithm}
%\algrenewcommand{\algorithmicrequire}{\textbf{Input:}}
%\algrenewcommand{\algorithmicensure}{\textbf{Output:}}
%\algrenewcommand{\algorithmicforall}{\textbf{for each}}
%
%\begin{algorithm}[H]
%\small
%\begin{algorithmic}[1]
%	\Require An undirected tree $G_{T} = (V,E)$
%	\Ensure A $k$-coloring for $G_{T}$.
%	\newline
%
%	\Procedure{\textsc{Dfs}}{$G_{T}$}
%		\ForAll{vertex $u \in V[G_{T}]$}
%			\State $c[u] \gets 0$ \Comment{paint initially all vertices with color $0$ s.t. $0 \notin \{1,\ldots, k\}$.}
%			\State $\pi[u] \gets \text{\textsc{null}}$ \Comment{set initially the predecessor of $u$ to \textsc{null}.}
%		\EndFor
%		\State $time \gets 0$ \Comment{initialize the global timestamp variable.}
%		\ForAll{vertex $u \in V[G_{T}]$}
%						\If{$c[u] = 0$}
%				\State \textit{call} \textsc{Dfs-Visit}($u$)
%			\EndIf
%		\EndFor
%	\EndProcedure
%	\newline
%
%	\Procedure{\textsc{Dfs-Visit}}{$u$}
%		\Statex\Comment{vertex $u$ with color $0$ has been discovered; then paint vertex $u$ with color $i \in \{1,\ldots,k\}$.}
%		\State $c[u] \gets i \in \{1,\ldots,k\} \text{ s.t. } c[u] \neq c[\pi[u]]$, i.e. $i \in \{1,\ldots,k\}\backslash \{c[\pi[u]]\}$
%		\State $d[u] \gets time \gets time + 1$ \Comment{update the discovering time.}
%		\ForAll{$v \in Adj[u]$} \Comment{explore edge $(u,v)$.}
%		   	\If {$c[v] = 0$}
%				\State $\pi[v] \gets u$
%				\State \textit{call} \textsc{Dfs-Visit($v$)}
%			\EndIf
%		 \EndFor
%		 \State $f[u] \gets time \gets time + 1$ \Comment{update the finishing time; $\Rightarrow$ search in $Adj[u]$ is finished.}
%	\EndProcedure	
%\end{algorithmic}
%\caption{\small Polynomial time DFS-Algorithm for $k$-Coloring of trees.}
%\label{alg_k-coloring_dfs}
%\end{algorithm}}}%
%BeginExpansion
\floatname{algorithm}{Algorithm}
\algrenewcommand{\algorithmicrequire}{\textbf{Input:}}
\algrenewcommand{\algorithmicensure}{\textbf{Output:}}
\algrenewcommand{\algorithmicforall}{\textbf{for each}}

\begin{algorithm}[H]
\small
\begin{algorithmic}[1]
	\Require An undirected tree $G_{T} = (V,E)$
	\Ensure A $k$-coloring for $G_{T}$.
	\newline

	\Procedure{\textsc{Dfs}}{$G_{T}$}
		\ForAll{vertex $u \in V[G_{T}]$}
			\State $c[u] \gets 0$ \Comment{paint initially all vertices with color $0$ s.t. $0 \notin \{1,\ldots, k\}$.}
			\State $\pi[u] \gets \text{\textsc{null}}$ \Comment{set initially the predecessor of $u$ to \textsc{null}.}
		\EndFor
		\State $time \gets 0$ \Comment{initialize the global timestamp variable.}
		\ForAll{vertex $u \in V[G_{T}]$}
						\If{$c[u] = 0$}
				\State \textit{call} \textsc{Dfs-Visit}($u$)
			\EndIf
		\EndFor
	\EndProcedure
	\newline

	\Procedure{\textsc{Dfs-Visit}}{$u$}
		\Statex\Comment{vertex $u$ with color $0$ has been discovered; then paint vertex $u$ with color $i \in \{1,\ldots,k\}$.}
		\State $c[u] \gets i \in \{1,\ldots,k\} \text{ s.t. } c[u] \neq c[\pi[u]]$, i.e. $i \in \{1,\ldots,k\}\backslash \{c[\pi[u]]\}$
		\State $d[u] \gets time \gets time + 1$ \Comment{update the discovering time.}
		\ForAll{$v \in Adj[u]$} \Comment{explore edge $(u,v)$.}
		   	\If {$c[v] = 0$}
				\State $\pi[v] \gets u$
				\State \textit{call} \textsc{Dfs-Visit($v$)}
			\EndIf
		 \EndFor
		 \State $f[u] \gets time \gets time + 1$ \Comment{update the finishing time; $\Rightarrow$ search in $Adj[u]$ is finished.}
	\EndProcedure	
\end{algorithmic}
\caption{\small Polynomial time DFS-Algorithm for $k$-Coloring of trees.}
\label{alg_k-coloring_dfs}
\end{algorithm}%
%EndExpansion

The algorithm (\ref{alg_k-coloring_dfs}) works as follows:

Lines 2--5 paint all vertices with the color $0\notin \{1,,\ldots ,k\}$ and
initialize their predecessor (parent node) to \textsc{Null}. Line 6
initializes the global time counter with $0$. The lines 7--11 check each
vertex in $V$, if a vertex $u$ with color $0$ is found, then this node will
be visited by calling \textsc{Dfs-Visit}. Every time when \textsc{Dfs-Visit}$%
(u)$ is called in line 9, vertex $u$ becomes root of a new tree in the
depth-first forest. Hence, when the procedure \textsc{Dfs} returns, every
node $u$ has been assigned with a discovery time $d[u]$ and a finishing time 
$f[u]$.

In \textsc{Dfs-Visit}$(u)$, the vertex $u$ is initially colored with color $%
0\notin \{1,,\ldots ,k\}$. The line 14 paints node $u$ with a color $i\in
\{1,\ldots ,k\}\text{ s.t. }c[u]\neq c[\pi \lbrack u]]$, i.e. $i\in
\{1,\ldots ,k\}\backslash \{c[\pi \lbrack u]]\}$. Afterwards, line 15
records the discovery time $d[u]$ by incrementing\ and saving the global 
\textit{time} variable. The lines 16--21 examine each vertex $v$ which is
adjacent to $u$ and visit $v$ recursively, if $v$ is colored with $0$. Since
in line 16 each vertex $v\in Adj(u)$ is considered, then each edge $(u,v)$
will be \textit{explored} by the depth-first search. After every edge
leaving $u$, with color $i\in \{1,\ldots ,k\}\backslash \{c[\pi \lbrack
u]]\} $, has been explored, finally the last line 22 update and records the
finishing time in $f[u]$.

The \textsc{Dfs} procedure takes a run time of $O(|V|)$, exclusive of the
time to execute the call of the \textsc{Dfs-Visit} procedure. The procedure 
\textsc{Dfs-Visit} will be called exactely once for each vertex $v\in V$. 
\textsc{Dfs-Visit} is invoked only on nodes which are colored with $0$ and
paint them subsequently with a color $i\in \{1,\ldots ,k\}\backslash \{c[\pi
\lbrack u]]\}$. During the execution of \textsc{Dfs-Visit}$(u)$, the
for-loop on lines 16--21 is executed $|Adj[v]|$ times and hence%
\begin{equation*}
O(|E|)=\dsum\limits_{v\in V}|Adj(v)|.
\end{equation*}

Then the total running time of \textsc{Dfs} is $O(|V|+|E|)$ which is in
polynomial time.

\bigskip

\begin{exercise}
\label{ex:Nqueens} Provide a reduction of \textbf{N-Queens} problem to 
\textbf{SAT}. Give a proof sketch of the correctness of your reduction. Does
this implies that the \textbf{N-Queens} is an $\mathsf{NP}$-complete
problem? Argue your answer.

\smallskip

\noindent In the \textbf{N-Queens} problem we are given $n$ queens and an $n
\times n$ chessboard. We ask whether we can place these $n$ queens on the
chessboard such that no two queens attack each other. Two queens attack each
other if they are placed in the same row, or in the same column, or in the
same diagonal.
\end{exercise}

%$$F=\bigwedge_{z=1}^{9}\Bigg(\bigvee_{y=1}^{9} v_{1,y,z}\Bigg)$$

\subsubsection{Reduction}

We have to construct a polynomial-time reduction from \textbf{N-Queens} to
SAT. Let an arbitrary instance of \textbf{N-Queens} be given by n queens and
a $n\times n$ chessboard. We construct a propositional formula $\psi $ (i.e.
an instance of \textbf{SAT}) as follows.\newline
First of all, we use the following propositional variables: $s_{i,j}$, where 
$s_{i,j}$ stands for the cell $(i,j)$ of the $n\times n$ chessboard. The
variable $s_{i,j}$ is assigned \textit{true} iff a queen is assigned to the
cell $c(i,j)$. The different constraints of the puzzle can be expressed with
this representation in the following way:

\noindent Rule to assert that we get at most one queen in a column: 
\begin{equation*}
\psi_1 \equiv
\bigwedge_{i=1}^{n}\bigwedge_{j=1}^{n}\bigwedge_{k=j+1}^{n}(\neg s_{i;j}
\vee \neg s_{i;k})
\end{equation*}

\noindent Rule to assert that we get at most one queen in each row: 
\begin{equation*}
\psi_2 \equiv
\bigwedge_{i=1}^{n}\bigwedge_{j=1}^{n}\bigwedge_{k=j+1}^{n}(\neg s_{j;i}
\vee \neg s_{k;i})
\end{equation*}

\noindent Left-lower to right-upper diagonal lines are splitted in two
parts: The bottom lines are characterized by a numer $d\in {0,...,n-2}$, and
each line is compounded by the cells $c(i,j)$ such that $i-j=d$. Notice that
the lines with only one cell (the corners) are removed.\newline
Rule to assert that we get at most one queen in a diagonal line: 
\begin{equation*}
\psi _{3}\equiv
\bigwedge_{d=0}^{n-2}\bigwedge_{j=1}^{n-d}\bigwedge_{k=j+1}^{n-2}(\lnot
s_{d+j;i}\vee \lnot s_{d+k;k})
\end{equation*}

\noindent The remaining diagonal lines are characterized by $d \in {%
-(n-2),...,-1}$ and their rule is defined by: 
\begin{equation*}
\psi_4 \equiv
\bigwedge_{d=2-n)}^{-1}\bigwedge_{j=1}^{n+d}\bigwedge_{k=j+1}^{n+d}(\neg
s_{j;j-d} \vee \neg s_{k;k-d})
\end{equation*}

\noindent Analogously the left-upper to right-lower diagonal lines are
splitted in two parts: The bottom lines are charactarized by a number $d \in 
{3,...,n+1}$ and the\newline
rule to assert that we get at most one queen in a diagonal line: 
\begin{equation*}
\psi_5 \equiv
\bigwedge_{d=3}^{n+1}\bigwedge_{j=1}^{d-1}\bigwedge_{k=j+1}^{d-1}(\neg
s_{dj;d-j} \vee \neg s_{k;d-k})
\end{equation*}

\noindent The remaining diagonal lines are characterized by $d \in {%
n+2,...,2n-1}$ and their rule is defined by: 
\begin{equation*}
\psi_6 \equiv
\bigwedge_{d=n+2}^{2n-1}\bigwedge_{j=d-n}^{n}\bigwedge_{k=j+1}^{d-1}(\neg
s_{j;d-j} \vee \neg s_{k;d-k})
\end{equation*}

\noindent Rule to assert that we get at least one queen in each column: 
\begin{equation*}
\psi_7 \equiv \bigwedge_{i=1}^{n}\bigvee_{j=i}^{n}s_{i;j}
\end{equation*}
wich ensures that there is exactly one queen in each column.

\noindent So we get the conjunction of these seven formulae: 
\begin{equation*}
\varphi \equiv \psi _{1}\bigwedge \psi _{2}\bigwedge \psi _{3}\bigwedge \psi
_{4}\bigwedge \psi _{5}\bigwedge \psi _{6}\bigwedge \psi _{7}\bigwedge
\end{equation*}%
is in CNF form and each truth assignment which makes it true represents a
solution to the \textbf{N-Queens} problem.

\subsubsection{Proof sketch}

We have to show that following equantion holds:%
\begin{equation*}
\varphi \text{ is a positive of }\mathbf{N-Queens}\text{ }\quad \iff \quad
\varphi _{S}\text{ is a positive instance of }\mathbf{SAT}\text{.}
\end{equation*}%
(i.e. both formuals $\varphi $ and $\varphi _{S}$ are \textit{%
equi-satisfiable}.)

\medskip

Then

\medskip

$\Rightarrow $ direction:\newline
Suppose that $\varphi $ is a positive instance of \textbf{N-Queens} and now
we have to show that $\varphi _{S}$ also is a positive instance of \textbf{%
SAT}.\newline
The formula $\varphi $ eavaluates to \textit{true} iff all clauses $\psi
_{i} $, $1\leq i\leq 7$, evaluates to \textit{true}. Therefore, we have to
show, that $\exists $ a truth assignment $T$ such that all clauses in $%
\varphi $ evaluates in to true under the truth assignment $T$. We define as
follows:\newline
\begin{equation*}
T(s_{i,j})=\left\{ 
\begin{array}{cl}
true & \text{ if }\exists \text{ a Queen }q\text{ on }c(i,j)\text{ and }%
\#(N-Queens)=n, \\ 
false & \text{otherwise.}%
\end{array}%
\right.
\end{equation*}

$\psi _{1}$ evaluates to true if for each number $j\in {1,..,n}$ the number
has been assigned at most once which is true for a positive instance of 
\textbf{N-Queens}. In this case every number will be assigned, exactly once,
therefore this clause evaluates to true.

Analogously this works for $\psi _{2}$.

$\psi _{3}$ evaluates to true if for each number $d\in {1,..,n-1}$ the
number has been assigned at most once which is also true for a positive
instance of \textbf{N-Queens}.

Analogously this works for $\psi _{4}$ to $\psi _{6}$.

$\psi _{7}$ evaluates to true if for each number $j\in {1,..,n}$ the number
has been assigned at least once which is true for a positive instance of 
\textbf{N-Queens}.

Finally, we have to show that $\varphi $ is equisatisfialbe to $%
\varphi _{S}\in \,$\textbf{SAT} by showing that there exists a function $\mu
:s_{i,j}\rightarrow v$, $\forall s_{i,j}\in \varphi $ and $\forall v\in
\varphi _{S}$, such that $\varphi _{S}$ evaluates to true.

$\Leftarrow $ direction:

Suppose, we have a positive instance $\varphi _{S}$ of \textbf{SAT.} We have
to show that it's possible to derive a poitive instance $\varphi \in $ 
\textbf{N-Queens} out of a truth-assignment $T$.

Similar as above, we have to build here also a truth-assignment function $T$
such that, $\varphi _{S}$ evaluates to true. Since $\varphi _{S}$ is a
positive instance of \textbf{SAT}, each clause of $\varphi _{S}$ will
evaluate to \textit{true}.

Then we have to show that there exists a function $\mu :v\rightarrow s_{i,j}$%
, $\forall v\in \varphi _{S}$ and $\forall s_{i,j}\in \varphi $, such that $%
\varphi \in $ \textbf{N-Queens} evaluates to true.

Hence, we can derive a queen set on an $n\times n$ chessboard by using the
first 6 clauses. Finally, we have to show that we can derive indeed a
positive instance of \textbf{N-Queens} out of $\mu $ and that the instance
of \textbf{N-Queens} has an exactly size of $n$.

\medskip

By definition of clauses $\psi _{1}$ to $\psi _{6}$ we already made sure
that there can be at most $1$ queen in each line, each row and each diagonal
line. Because of clause $\psi _{7}$ there must be at least one queen in each
column and therefore we can be sure that \textbf{N-Queens} is of size $n$.

\subsubsection{NP-complete}

Yes, \textbf{N-Queens} is NP-complete because we have constructed a
polynomial-time reduction of \textbf{N-Queens} problem to \textbf{SAT} and 
\textbf{SAT} is NP-complete, which is a well-known fact.

\bigskip

\begin{exercise}
Consider the following problem:

\fbox{ 
\begin{minipage}[c]{.95\linewidth}
        \textbf{N-SORTED-ELEMENTS}

        \medskip

        INSTANCE: A non-empty list $L=(e_1,\ldots,e_n)$ of non-negative integers. \\
        QUESTION: Does the list $L$ contain a sub-list of $k$ consecutive sorted numbers in ascending order (from left to right)?
      \end{minipage}
    }

\medskip Argue that \textbf{N-SORTED-ELEMENTS} can be solved using only
logarithmic space.
\end{exercise}

This can be explained by using a small procedure (see Procedure \ref%
{Alg-N-Sorted-El}) for this problem.

%TCIMACRO{%
%\TeXButton{Algorithm: N-SORTED-ELEMENTS}{\floatname{algorithm}{Procedure}
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand{\algorithmicensure}{\textbf{Output:}}
%\renewcommand{\algorithmicforall}{\textbf{for each}}
%
%\begin{algorithm}[ht]
%\small
%\begin{algorithmic}
%	\Require $L=(e_{1},\ldots , e_{n}), k\in \mathbb{N}^{+}$
%	\Ensure $\mathbf{true}$ if $n$-sorted elements of size $k$ are found, $\mathbf{false}$ otherwise.
%	\newline
%	\State $i \leftarrow 1$
%	\State $count \leftarrow 1$ \Comment{count variable for finding $n$-sorted elements of size $k$.} 
%	\ForAll{$i \;$ s.t. $\; 1 \leq i \leq |L| - 1$}
%		\If{$\left(e(i) + 1\right) = e(i+1)$}
%			\State $count \leftarrow count + 1$
%		\Else
%			\If{$count = k$}
%				\Return \textbf{true}
%			\Else
%				\State $count \leftarrow 1$ \Comment{the number of sorted elements was $< k$; $\Rightarrow$ reset the count value.}
%			\EndIf
%		\EndIf
%	\EndFor\\
%	\Return \textbf{false}	
%\end{algorithmic}
%\caption{\small \textsc{N-Sorted-Elements} procedure.}
%\label{Alg-N-Sorted-El}
%\end{algorithm}}}%
%BeginExpansion
\floatname{algorithm}{Procedure}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\renewcommand{\algorithmicforall}{\textbf{for each}}

\begin{algorithm}[ht]
\small
\begin{algorithmic}
	\Require $L=(e_{1},\ldots , e_{n}), k\in \mathbb{N}^{+}$
	\Ensure $\mathbf{true}$ if $n$-sorted elements of size $k$ are found, $\mathbf{false}$ otherwise.
	\newline
	\State $i \leftarrow 1$
	\State $count \leftarrow 1$ \Comment{count variable for finding $n$-sorted elements of size $k$.} 
	\ForAll{$i \;$ s.t. $\; 1 \leq i \leq |L| - 1$}
		\If{$\left(e(i) + 1\right) = e(i+1)$}
			\State $count \leftarrow count + 1$
		\Else
			\If{$count = k$}
				\Return \textbf{true}
			\Else
				\State $count \leftarrow 1$ \Comment{the number of sorted elements was $< k$; $\Rightarrow$ reset the count value.}
			\EndIf
		\EndIf
	\EndFor\\
	\Return \textbf{false}	
\end{algorithmic}
\caption{\small \textsc{N-Sorted-Elements} procedure.}
\label{Alg-N-Sorted-El}
\end{algorithm}%
%EndExpansion

The above procedure can be solved in logarithmic space in the size of the
input $I$ with $|I|=|L|$.\newline
\noindent The procedure needs only one pointer to an element in the list $L$
and one count variable of constant size. I.e. the pointer variable $i$ need $%
\log (n) $ bits for its representation. Observe a very large list $L$ of
non-negative intergers. Since the memory of a program is limited to constant
many pointers, the pointer variable $i$ uses at most $O(\log _{2}|L|)$ bits
of memory.

\bigskip

\begin{exercise}
\label{ex:turing}

Design a Turing machine that increments by one a value represented by a
string of 0s and 1s.
\end{exercise}

\end{document}