\documentclass[a4paper,twoside]{article}
\usepackage[english]{babel}
\usepackage[cp1250]{inputenc}
\usepackage{a4wide}
%Veci pro matiku
\usepackage{amsmath, amsthm, amssymb}
%Vkladani obrazku atd.
\usepackage{graphicx}
%Vypisy pseudokodu
\usepackage{algorithmic}
%litingy - vypisy zdrojoveho kodu.
\usepackage{listings}
%potreba pro ramecek se zdrojakem
\usepackage {fancyvrb}
\providecommand{\OO}[1]{\operatorname{O}\bigl(#1\bigr)}
\author{Štěpán~Šindelář}
\title{Assignment Advanced Computational Complexity -- Stepan Sindelar}
\begin{document}
\subsection*{Assignment: Advanced Computational Complexity -- Stepan Sindelar}
\paragraph*{Question 1.}
\subparagraph*{}
The complement language for \emph{LARGES INDEPENDENT SET} decision problem is
the language of are all strings that encode positive answers to question:
'Is not $W$ a maximum size independent set for $G$?',
which can be formulated as 'Is not $W$ an independent set or
is there any other independent set of size at least $|W|+1$?'.
Verification that $W$ is independent set is polynomial and
we can use \emph{INDEPENDENT SET} decision problem from the
previous set of exercises (shown to be $NP$-complete) to
find out whether there is an independent set of size $|W|+1$.
(If there is a maximal size independent set of size $n > |W|$,
than there must be independent set of size $|W|+1$ -- we
can just forget some vertices from the maximal one and the rest
should be still independent.)
\paragraph*{Question 2.}
\subparagraph*{}
\paragraph*{Question 5.}
\subparagraph*{Reduction to \emph{HAMILTONIAN CYCLE}.}
We want the zero-weight-cycle to go through all the vertices.
NOTES:
- ascribe each vertex number like 1, 10, 100
- now each edge will contain sum of it's ednpoints' numbers
- two new vertices:
- v -- connected to all vertices, edges have value -max (the sum of those numbers)
- u -- connected to all vertices, edges have new 'vertex number' = x
- an edge {u,v} will have value -x
- as long as it visits one edge, it must visit all the others to get 0
-- totally the same for SUBSETSUM
today: c'mon man you CAN do it:
- Finish Reversi minimax with until alpha-b
- Complexity Formative
- English mate - vocab recap
- tutoring CS?
- Game Theory notes
- Vocabulary and pronunciation,
- Marias for Smart Phone
- Dart, Roslzn
- lenses
Google Summer of Code
http://www.infoq.com/presentations/Forget-about-Threads
\end{document}