PAA/part-2/2018.bonus.tex

\section{bonus - zadania z ćwiczeń}
\task{Jesteś na księżycu! Możesz wysłać tylko 5 symboli, jako komunikat o tym co właśnie odkryłeś. Przy założeniu, że
w problem $\Pi \in \NP$ przekaż wiadomość, mówiącą, że:}
\subtask{Złożoność dowolnego algorytmu deterministycznego rozwiązującego problem $\Pi$ jest $\Omega(2^n)$}
\subtask{$\Pi$ da się rozwiązać algorytmem deterministycznym w czasie $o(P)$}
\subtask{$\Pi \in \NPC$ i istnieje deterministyczny algorytm wielomianowy rozwiązujący ten problem.}
\subtask{\alphareduction{\problem{3SAT}}{$\Pi$}}
\subtask{\alphareduction{$\Pi$}{\problem{3SAT}}}

\begin{solution}
Wiemy, że nasz problem $\Pi \in \NP$ istnieje więc niedeterministyczny algorytm wielomianowy, który jest w stanie
go rozwiązać. Mamy pewność, że złożoność dowolnego algorytmu \textbf{deterministycznego} jest $\Omega(2^n)$ czyli
ograniczona przez funkcję wykładniczą z dołu. Ponieważ każda funkcja wykładnicza o podstawie większej niż 1
rośnie szybciej niż dowolna funkcja wielomianowa wiemy, że na pewno nie ma \textbf{deterministycznego} algorytmu
rozwiązującego nasz problem $\Pi$ w czasie wielomianowym co znaczyłoby, że $\Pi \not \in \P$. Łącząc to z założeniem
otrzymalibyśmy, że problem $\Pi$ jest w \NP a nie jest w \P, czyli:
\begin{center}
    $\mathtt{P \neq NP}$ - 4 symbole
\end{center}

Jeżeli natomiast $\Pi$ da się rozwiązać algorytmem deterministycznym w czasie $o(P)$, gdzie $P$ to jakiś wielomian
to z definicji klasy \P
\begin{center}
    $\Pi \in \P$ - 3 symbole
\end{center}

Jeżeli $\Pi \in \NPC$ to wiemy, że każdy problem z klasy \NP możemy sprowadzić do tego problemu w czasie wielomianowym.
Jeżeli dodatkowo potrafilibyśmy rozwiązać $\Pi$ w czasie wielomianowym to łączny potrzebny czas na rozwiązanie
dowolnego problemu \NP byłby sumą dwóch wielomianów - redukcji oraz rozwiązania $\Pi$ - czyli również wielomianem, a to
znaczyłoby że
\begin{center}
    $\NP = \P$ - 4 symbole
\end{center}

Problem \problem{3SAT} jest problemem \NPC, zatem jeżeli możemy wszystko $\alpha$-redukowac do \problem{3SAT} a
\problem{3SAT} możemy $\alpha$-redukować do $\Pi$ to na podstawie przechodniości relacji $\alpha$-redukcji do $\Pi$
możemy zredukować wszystko, czyli
\begin{center}
    $\Pi \in \NPC$ - 5 symboli
\end{center}

W ostatnim wypadku odkryliśmy, że da się zredukować problem $\Pi \in \NP$ do problemu, do którego da się zredukować
wszystkie problemy $\NP$ (zgodnie z definicją klasy \NPC). W takim wypadku lepiej nie wysyłajmy nic.
\begin{center}
    0 symboli
\end{center}
\end{solution}

\task Podaj status problemów (tj. czy są \P czy \NP-trudne) optymalizacyjnych podanych poniżej w podziałem na ich wersje maksymalizacyjne oraz wersje
minimalizacyjne.
\subtask Kolorowanie wierzchołków w grafie
\subtask Znalezienie $k$-tego największego/najmniejszego elementu
\subtask Problem komiwojażera
\subtask Drzewo spinające
\subtask Największa/najmniejsza droga w grafie
\subtask Klika w grafie planarnym

\begin{solution}
Biorąc pod uwagę, że jedynym wymaganiem kolorowania wierzchołków w grafie jest to, żeby 2 sąsiednie wierzchołki nie
miały tego samego koloru to wersja maksymalizacyjna problemu jest problemem wielomianowym - wystarczy każdy
wierzchołek pokolorować na inny kolor, co da nam maksymalną możliwą liczbę kolorów. Wersja decyzyjna problemu
kolorowania wierzchołków jest natomiast problemem \NPC zatem optymalizacyjnie jest to problem \NP-trudny.

Znalezienie $k$-tego najmniejszego bądź największego elementu jest zadaniem prostym pod warunkiem, że nasz zbiór jest
posortowany. Wiadomo, że sortowanie jest problemem $O(n\log n)$ zatem problem ten jest wielomianowy.

Problem komiwojażera bez względu na to czy jest minimalizacyjny czy maksymalizacyjny wymaga znalezienia cyklu hamiltona
w danym grafie - co jest zadaniem trudnym obliczeniowo - problem szukania cyklu hamiltona jest \NPC. Dodatkowo
musimy znaleźć cykl o największej bądź najmniejszej możliwie sumie wag - to znaczy, że problem ten musi być \NP-trudny.

Problem minimalnego drzewa spinającego można rozwiązać algorytmem Kruskala. Jeżeli zastąpimy wybieranie minimalnej
krawędzi wybieraniem krawędzi maksymalnej to otrzymamy algorytm szukający maksymalnego drzewa spinającego. Kruskal jest
algorytmem wielomianowym, zatem cały problem jest w klasie \P.

Znalezienie najkrótszej drogi w grafie jest bardzo proste, wystarczy wziąć dowolną krawędź - nie da się zrobić ścieżki
krótszej niż 1. Szukanie najdłuższej ścieżki już takie proste nie jest. W grafie jest $n$ wierzchołków, maksymalna
droga jaką możemy stworzyć bez tworzenia cyklu to droga $n$ wierzchołkowa, zawierająca $n-1$ krawędzi. Ścieżka, która
przechodzi przez dokładnie wszystkie wierzchołki jest ścieżką hamiltona, a problem ścieżki hamiltona jest problemem \NPC.
Zatem zakładając, że rozpatrujemy wersję decyzyjną tego problemu zdefiniowaną następująco: ,,W grafie $G$ istnieje
ścieżka długości $l$'' to dość łatwo możemy przeprowadzić $\alpha$-redukcję problemu ścieżki hamiltona do problemu
drogi w grafie - graf pozostaje bez zmian, natomiast za długość ścieżki przyjmujemy liczbę wierzchołków w grafie.
Wersja decyzyjna jest zatem \NPC, a co za tym idzie problem w wersji maksymalizacyjnej jest \NP-trudny.

Z twierdzenia Kuratowskiego wiemy, że żaden graf planarny nie może zawierać kliki $K_5$, zatem najwiekszą kliką w
planarnym grafie jest klika $K_4$. Jesteśmy w stanie sprawdzić istnienie $K_4, K_3$ w grafie w czasie wielomianowym.
Przypadki $K_1$ i $K_2$ są jeszcze łatwiejsze ponieważ klika $K_1$ to nic innego jak wierzchołek, a $K_2$ to krawędź.
Stąd też wiemy, że wersja minimalizacyjna jest \P.

\begin{table}[H]
    \centering
    \begin{tabular}{r|cccccc}
        problem & a & b & c & d & e & f \\ \hline
        $\min$ & \NP-trudny & \P & \NP-trudny & \P & \P & \P \\
        $\max$ & \P & \P & \NP-trudny & \P & \NP-trudny & \P
    \end{tabular}
    \caption{Podsumowanie statusów problemów z zadania}
\end{table}
\end{solution}

\task Masz dany graf $G$ oraz liczbę $k$. Czy graf $G$ zawiera klikę o rozmiarze $k$? Do pomocy masz czarną skrzynkę.
Możesz do niej włożyć tylko graf $G$ posiadający gwiazdę spinającą oraz liczbę $p$ będącą progiem. Skrzynka odpowie na
pytanie - ,,Czy w danym grafie istnieje klika o rozmiarze $k \geq p$?''. Jeżeli graf nie ma gwiazdy spinającej to
skrzynka milczy.

\tip{Gwiazda spinająca to inaczej wierzchołek połączony ze wszystkimi innymi wierzchołkami.}
\begin{solution}
Przypomnijmy że klika to graf pełny, czyli inaczej taki graf, w którym każdy wierzchołek jest połączony z każdym innym.
Co za tym idzie, aby zwiększyć klikę o 1 należy dodać nowy wierzchołek, który jest połączony ze wszystkimi innymi
już istniejącymi wierzchołkami.

Dodanie do grafu gwiazdy spinającej z definicji dodaje wierzchołek połączony ze wszystkimi innymi wierzchołkami.
\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{.5\linewidth}
        \centering
        \input{gfx/gwiazda-spinajaca.tex}
        \caption{Graf $G$}
        \label{fig:2018:3:G}
    \end{subfigure}%
    \begin{subfigure}[b]{.5\linewidth}
        \centering
        \input{gfx/gwiazda-spinajaca-2.tex}
        \caption{Graf $H$}
        \label{fig:2018:3:H}
    \end{subfigure}%
    \caption{Graf $H$ powstaje przez dodanie gwiazdy spinającej do grafu $G$}
\end{figure}

Zauważmy, że w grafie \ref{fig:2018:3:G} istnieje klika $K_4$ składająca się z wierzchołków $(1, 2, 6, 5)$. Ponieważ dodaliśmy gwiazdę
spinajacą klika razem z dodanym wierzchołkiem stanowi klikę $K_5$. Wiemy zatem, że po dodaniu do grafu gwiazdy spinającej
wszystkie kliki ,,awansują'' w rozmiarze o 1. Zatem aby sprawdzić czy w grafie przed dodaniem gwiazdy istnieje klika o
rozmiarze $n$ wystarczy sprawdzić czy w grafie $H$, istnieje klika o rozmiarze $p = n+1$.

Skrzynka odpowiada nam na pytanie czy w grafie istnieje klika $k \geq p$, jednak pamiętajmy, że zgodnie z powyższym
rozumowaniem mniejsze kliki są podgrafami klik większych, zatem nawet jeżeli skrzynka znajdzie podgraf $K_{10}$ a my
szukamy ledwo $K_5$ to i tak wiemy, że $K_5$ istnieje w $K_{10}$.
\end{solution}

\task Kierownik zmiany ma pod opieką $m = 4$ identycznych obrabiarek i $n$ różnych elementów do obrobienia. Na swoim
komputerze posiada PTAS o złożoności $O(n\log^{1/\varepsilon} n + m^m)$. Praca zaczyna się o 7:00 a o 15:00 jest mecz,
który chce obejrzeć. Wiemy, że optymalny czas pracy wynosi 6h, jaką złożoność będzie miał algorytm, który pozwoli
kierownikowi obejrzeć mecz?

\begin{solution}
Problem ten jest problemem minimalizacyjnym oraz wiemy, że $A_\text{opt} = 6$. Aby zdążyć obejrzeć mecz musimy skończyć
pracę o 15:00, zatem wystarczy że algorytm przydzieli pracę tak, aby wszystkie elementy zostały obrobione w czasie
8 godzin skąd $A = 8$.

\begin{equation*}
    \frac{A}{A_\text{opt}} \leq 1 + \varepsilon \iff A \leq A_\text{opt} + \varepsilon A_\text{opt}
\end{equation*}

Ponieważ nie chcemy męczyć naszego komputera, a dokładne obliczenia są coraz cięższe wystarczy że rozpatrzymy przypadek
rozwiązujący problem dla dokładnie 8 godzin:
\begin{equation}
    A = A_\text{opt} + \varepsilon A_\text{opt}
\end{equation}

Ponieważ znamy zarówno $A$ jak i $A_\text{opt}$ z łatwością możemy wyznaczyć $\varepsilon$
\begin{equation*}
    8 = 6 + 6\varepsilon \iff 2 = 6\varepsilon \iff \varepsilon = \frac{1}{3}
\end{equation*}

W taki sposób otrzymujemy złożoność $O(n\log^3 n + m^m)$, ponieważ $m$ jest stałe możemy pominąć je w obliczaniu
złożoności uzyskując ostatecznie $O(n\log^3 n)$.
\end{solution}

\task Na płaszczyźnie znajduje się n punktów, chcemy znelźć ich średnicę, czyli największą odległość pomiędzy dwoma z nich.
Następujący algorytm rozwiązuje ten problem w sposób 2-przybliżony. Udowodnij ten fakt.

\begin{column}{.6}
    \begin{algorithm}[H]
        \caption{Prosty algorytm do liczenia średnicy}
        \begin{algorithmic}[1]
            \For{i = 2,...,n}
                \State $d_{1,i} \gets $ odległość z punktu $1$ do $i$
            \EndFor
            \State \Return $\max \set{d_{1,2}, ..., d_{i,n}}$
        \end{algorithmic}
    \end{algorithm}
\end{column}
\begin{column}{.4}
    \begin{figure}[H]
        \centering
        \begin{tikzpicture}[every node/.style={above}]
            \draw (0, 0) node {1} -- (4, 0) node {2};
            \draw (1, 1) node {3} -- (3, 2) node {4};
        \end{tikzpicture}
        \caption{przykładowe punkty}
    \end{figure}
\end{column}

\begin{solution}
Aby rozwiązać ten problem najpierw spróbujmy rozważyc jego uporoszczoną wersję - w jednym wymiarze. W tym wypadku
rozwiązanie problemu zawsze będzie dość proste - średnica będzie między punktem wysuniętym najbardziej na lewo i punktem
najbardziej wysuniętym na prawo. Najprawdopodobniej jednak nasz punkt $1$ będzie znajdował się gdzieś między nimi.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[every node/.style={above}]
        \draw[*-*] (0, 0) node {$\alpha$} -- (2, 0) node {1};
        \draw[-*] (2, 0) -- (5, 0) node {$\Omega$};
    \end{tikzpicture}
\end{figure}

Na całą resztę zadania przyjmijmy, że punkty tworzące średnice nazwiemy $\alpha$ i $\Omega$, przy czym żaden z tych
punktów nie jest punktem $1$. Na powyższym rysunku, dość wyraźnie widać zależność

\begin{equation*}
    d_{\alpha,1} + d_{1,\Omega} = d_{\alpha,\Omega}
\end{equation*}

Ponieważ z par punktów $\alpha, 1$ i $1, \Omega$ zawsze wybieramy tę, między którymi jest większa odległość, możemy mieć
pewność że $d_{\alpha,\Omega} \leq 2\cdot d$, gdzie $d$ to wybrana przez nas średnica. $d_{\alpha,\Omega} = 2d$ gdy
punkt 1 znajduje się idealnie po środku.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[every node/.style={circle, fill, inner sep=1.5pt}]
        \coordinate (a) at (0,0);
        \coordinate (b) at (2,1);
        \coordinate (1') at (2, 0);
        \coordinate (c) at (5,0);

        \node[label={above:$\alpha$}] at (a) {};
        \node[label={above:$1$}] at (b) {};
        \node[label={below:$1'$}] at (1') {};
        \node[label={above:$\Omega$}] at (c) {};

        \draw[densely dotted] (a) -- (b) -- (c);
        \draw[dashed] (b) -- (1');
        \draw[thick] (a) -- (c);
    \end{tikzpicture}
\end{figure}

Z poprzednich rozważań wiemy, że w wypadku punktu oznaczonego teraz jako $1'$ algorytm może pomylić się maksymalnie
2-krotność swojej odpowiedzi. Odległość pomiędzy punktem 1 a jednym z punktów średnicy jest teraz na pewno większa
niż w wypadku $1'$ a co za tym idzie odpowiedź będzie bliższa tej poprawnej, czyli najgorszym wypadkiem wciąż pozostaje
pomyłka o 2-krotność odpowiedzi optymalnej, czyli algorytm jest 2-aproksymacyjny.
\end{solution}

\task Które ze zdań o powyższym problemie są prawdziwe?

\subtask Problem ten jest wielomianowy?
\subtask Problem ten jest \NPC
\subtask Problem ten jest \NP-trudny
\subtask Istnieje algorytm wielomianowy, który jest 1.5-aproksymacyjny
\subtask Istnieje algorytm wielomianowy, który jest 2.5-aproksymacyjny
\subtask Istnieje algorytm wielomianowy, który jest 2-absolutnie aproksymacyjny
\subtask Nie istnieje schemat PTAS

\begin{solution}
Aby znaleźć największą odległość między parami punktów na płaszczyźnie wystarczy sprawdzić wszystkie możliwe pary,
których jest ${n \choose 2} = O(n^2)$, algorytm zatem jest wielomianowy, czyli należy do klasy \P. Co za tym
idzie nie może być problemem \NPC a tym bardziej \NP-trudnym. Warto jednak zaznaczyć, że gdyby pytanie dotyczyło
tego czy problem ten jest \NP to odpowiedź byłaby twierdząca ponieważ $\P \subseteq \NP$.

Ponieważ problem jest wielomianowy, wszystkie aproksymacje są możliwe - chcąc uzyskać algorytm $x$-aproksymacyjny wystarczy,
że przemnożymy wynik dokładny przez $x$ - jest to operacją wielomianową ponieważ znalezienie wyniku dokładnego jest
wielomianowe a mnożenie tym bardziej. Tak samo możemy postąpić z absolutną aproksymacją - wystarczy dodać bądź odjąć $x$.

Zgodnie z powyższym, możemy uzyskać dowolnie dobre przybliżenie jakie chcemy czyli schemat PTAS powinien istnieć.
\textit{Za to stwierdzenie nie dam sobie głowy uciąć, słabo mieliśmy to omówione i nie wiem czy na pewno ma to sens.}

Odpowiedzi zatem klarują się następująco:
\begin{table}[H]
    \centering
    \begin{tabular}{l|l}
        Problem ten jest wielomianowy? & \textbf{TAK} \\
        Problem ten jest \NPC & \textbf{NIE} \\
        Problem ten jest \NP-trudny & \textbf{NIE} \\
        Istnieje algorytm wielomianowy, który jest 1.5-aproksymacyjny & \textbf{TAK} \\
        Istnieje algorytm wielomianowy, który jest 2.5-aproksymacyjny & \textbf{TAK} \\
        Istnieje algorytm wielomianowy, który jest 2-absolutnie aproksymacyjny & \textbf{TAK} \\
        Nie istnieje schemat PTAS & \textbf{NIE} \\
    \end{tabular}
\end{table}
\end{solution}