source: liacs/comp/opdracht-3.tex@ 30

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\usepackage{amssymb,amsmath,amsthm}
\selectlanguage{dutch}

\author{Rick van der Zwet, Universiteit Leiden}
\title{Complexiteit\\
\large{Derde huiswerkopgave}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden University\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}


\begin{document}
\appendix
\maketitle
\section*{Inleiding}
Het doel van deze huiswerkopgave is het begrijpen en toepassen van
niet-deterministische algoritmen en kennis maken met de begrippen
$NP$-compleet en $NP$-volledig. Deze kennis wordt opgedaan door te
kijken naar 2 verschillende problemen:

\theoremstyle{definition} \newtheorem{sat}{SAT}
\newtheorem{mcis}{MaxColorIndependentSet (MCIS)}

\begin{description}
\item[SAT] Gegeven is een logische expressie $\phi$ in de variablen
$x_1, x_2,..., x_n$ in CNF (dus een AND van clausules waarbij elke
clausule de OR van een willekeurig aantal literals is; een literal is
een $x_1$ of een $\neg x_1$). \\
Vraag: is er een waardering (waarheidstoekenning) van de $x_i$'s zodanig
dat $\phi$ wordt waargemaakt, dat wil zeggen dat per clausule minstens
\'e\'en literal waar is?
\item[MaxColorIndependentSet (MCIS)] Gegeven een ongerichte graaf
$G=V(,E)$, waarbij de knopen wit of zwart gekleurd zijn. $V$ bevat dus
de knopen m\`et hun kleur. \\ 
Vraag: bestaat er een maximaal onafhankelijke knoopverzameling $I (I
\subseteq V)$ die alleen zwarte knopen bevat? \\
Een deelverzameling $J$ van de knopen $V$ heet \emph{onafhankelijk} als
geldt: voor alle $i,j \in J$ is er \emph{geen} tak tussen $i$ en $j$.
Zo'n onafhankelijke verzameling is \emph{maximaal} als er geen knopen
meer aan kunnen worden toegevoegd zonder dat de
onafhankelijkheidseigenschap verloren gaat.
\end{description}


\section{\normalsize Laat zien dat MCIS $\in NP$ door een \emph{niet-deterministisch
polynomiaal} algoritme voor MCIS te geven.}
Het algoritme bestaat uit drie fases:
\begin{description}
\item[Fase 1 (gokfase)]
Genereer een random string $s$ gehele getallen welke als de volgende
syntax wordt geinterpeteerd $knoopnummer;kleur;lid MCIS;buren;$
\item[Fase 2 (verificatiefase)]
Er wordt gecontroleerd of $s$ daarwerkelijk een MCIS is:
\begin{enumerate}
\item controleer dat er precies $n$ knopen in staan: $O(\left|s\right|)$
\item controleer of kleurcode wit/zwart (1/0) is: $O(\left|s\right|)$
\item controleer of elke knoop tussen 0 en $n$ ligt: $O(\left|s\right|)$
\item controleer of alle knopen verschillend zijn: $O({\left|s\right|}^2)$
\item controleer of alle buren geldig zijn: $O({\left|s\right|}^2)$
\item controleer of knop welke lid is, zwart is: $O(\left|s\right|)$
\item controleer of alle buren van zwarte `lid' knoop niet lid zijn:
    $O({\left|s\right|}^2)$
\item controleer of alle niet `lid' knopen, buren zijn van een `lid'
knoop: $O({\left|s\right|}^2)$
\end{enumerate}
Stap 1 t/m 5 zijn eigenlijk simpele controle stapjes om te kijken of de
invoer string voldoet aan de eisen die gesteld worden. De daadwerkelijke
intelligentie zit in de laatste stappen, welke kijkt of de eisen van de
zwarte MCIS voldaan worden. Dat wil zeggen zoveel mogelijk knopen die
geen buurtjes van elkaar zijn en geen witte knopen in de `leden' kring.

\item[Fase 3]
Als Fase 2 True opleverd (e.g. alle punten goed doorlopen) wordt ``ja''
uitgevoerd, anders geen uitvoer.
\end{description}

In de meeste stappen van het algoritme volstaat een keer doorlopen van
$s$ als voldoende, bijvoorbeeld bij controle kleur invoer. Bij het de
buren controle echter moet per item in $s$ de string nog een keer extra
worden doorlopen om te kijken of deze knoop daarwerkelijk voorkomt. Maar
in het totaal is $O({\left|s\right|}^2)$ voldoende.

\section{\normalsize Laat zien dat de transformatie $T$ in polynomiaal begrensde
tijd uitgevoerd kan worden}
$T$ is hierbij de transformatie van SAT naar MCIS, waarbij $\phi$ een
logische expressie in de variablen $x_1, x_2,..., x_n$ in conjunctieve
normaalvorm (CNF). Daaruit wordt een een ongerichte graag $G_\phi$
geconstrueerd, waarvan de knopen zwart of wit gekleurd zijn. Maak 2$n$
zwarte knopen, corresponderd met de $n$ voorkomende variablen en hun
negaties (alle mogelijke literals dus). Voor elke in $\phi$ voorkomende
clausule komt een witte knoop. Elke witte knoop wordt verbonden met de
(zwarte) knopen die corresponderen met de in de betreffende clausule
voorkomende literals ($x_i$ and $\neg x_i$). Defineer nu $T(\phi) =
G_\phi$

De stappen noodzakelijk zijn:
\begin{enumerate}
\item Alle clausulen tellen en witte knopen maken voor elke clausule:
$O(\phi)$
\item Door de clausulen lopen en zwarte knopen maken en hun negaties:
$O(\phi)$
\item Clausule knoop met literal knopen verbinden: $O(\phi)$
\item Tak aanleggen tussen aanwezige complementaire literals $O({\phi}^2)$
\end{enumerate}

Dit allen is dus uit te voeren in $O({\phi}^2)$

\section{\normalsize Bewijs: als er een waardering $w$ van de $x_i$ bestaat die
$\phi$ waarmaakt, dan heeft $G_\phi$ een maximale onafhankelijke
knoopverzameling die alleen uit zwarte knopen bestaat}

Als $w$ waar is dan geld dat voor elke clausule $C_r$ een literal heeft die
minimal waargemaakt moet worden wil $\phi$ True worden. Alle
$l_i^r$ hebben een corresponderende knoop $v_i^r$ in $G_\phi$. Echter de
literals (zwarte knopen) kunnen niet met elkaar verbonden zijn, vanwege
de complementaire eigenschap. Dit betekend dat van een paar $l_i^r$ en
$\neg l_i^r$ slecht een enkele actief kan zijn.
Het maximale eigenschap wordt bereikt doordat knopen binnen dezelfde
clausule van elkaar gescheiden zijn van een $C$ (witte clausule) knoop.


\section{\normalsize Bewijs: als $G_\phi$ een maximale onafhankelijke
knoopverzameling $J$ heeft die alleen uit zwarte knopen bestaat, dat is
er een waardering $w$ van de $x_i$ die $\phi$ waarmaakt}

Kies $w$ van de in $\phi$ voorkomende logische variablen die precies
True oplevert op litterals correspondered met de knopen in $G_\phi$. In
$w$ zullen $m$ clausulen voorkomen. Deze $m$ witte knopen zullen altijd
verbonden zijn met een knoop $\in J$.Doordat elke cluasule waar moet
zijn zal er altijd een knoop bevinden tussen de witte cluasule knopen en
minstens \'e\'en van de literals.




\end{document}