% % $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{}\\ \\ 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}