problemynp.tex

\section{Problemy NP} %albo NP-zupełność, nie jestem pewien co do nazwy
Na wstępie chcielibyśmy zaznaczyć że tematyka NP-zupełności nie będzie poruszana dogłębnie. 
Nie będziemy np. wprowadzać definicji maszyny Turinga(lub innego modelu) oraz przeprowadzać skomplikowanych dowodów, gdyż wymagałoby to wiedzy z zakresu teorii języków formalnych i złożoności obliczeniowej. 
Zamiast tego będziemy chcieli nabrać trochę intuicji co do tego czy w ogóle warto starać się rozwiązywać dany problem czy może jest to strata naszego czasu.
\\
\\ \noindent
\begin{definition}
Problemem decyzyjnym nazywamy problem którego rozwiązanie przyjmuje jedną z dwóch wartości - $TAK, NIE$
\end{definition}
\noindent
Zauważmy że problemy decyzyjne możemy utożsamiać z podzbiorami pewnego uniwersumi, w ten sposób że problem jest zbiorem wartości, dla których odpowiedź to $TAK$.
\\ \noindent
\b{PRZYKŁAD}. Problem polegający na rozstrzygnięciu czy dana liczba naturalna $p$ jest liczbą pierwszą utożsamilibyśmy ze zbiorem liczb pierwszych.

\begin{definition}
Dla danej funkcji kosztu $f$, problemem optymalizacyjnym nazywamy problem którego rozwiązaniem jest wartość z danego uniwersum, minimalizująca wartość funkcji kosztu.
\end{definition}
\noindent
\b{PRZYKŁAD}. Dla danego grafu $G$ oraz wierzchołków $u$ i $v$, wyznaczyć najkrótszą drogę między $u$ i $v$. 
Naszą funkcją kosztu jest długość drogi,a uniwersum to wszystkie drogi łączące $u$ i $v$.

% TODO napisać cos o związkach między problemami decyzyjnymi i optymalizacyjnymi

\begin{definition}[Klasa $NP$]
Klasą $NP$ nazywamy zbiór problemów decyzyjnych $L$ t. że istnieje algorytm wielomianowy $A$ dla którego prawdziwe jest następujące zdanie:
\begin{center}
$x \in L \iff $ istnieje $y$ t. że $|y| < |x|^c$ oraz $A$ akceptuje $(x,y)$
\end{center}
\end{definition}
\noindent
W powyższej definicji możemy myśleć o $y$ jako o podpowiedzi dla algorytmu, lub nawet gotowym rozwiązaniu, natomiast $A$ jest weryfikatorem, który używając podpowiedzi próbuje udzielić odpowiedzi, gdzie $A$ akceptuje $(x,y)$ oznacza że odpowiedź dla danych wejściowych $x$ to $TAK$.
% TODO dodać cos o długości, bądź też rozmiarze wejścia (|.|)
\\
\\ \noindent
\b{PRZYKŁAD}. Pokażmy że problem decyzyjny, polegający na sprawdzeniu czy w grafie $G$ istnieje cykl Hamiltona jest w $NP$.
\begin{proof}
Najpierw musimy wymyślić weryfikator, tzn. wielomianowy algorytm sprawdzający istnienie cyklu Hamiltona w grafie. 
Nasz będzie dość prosty - dla danego grafu $x$, oraz $y$ - pewnej drogi w $x$, zwyczajnie sprawdzimy czy $y$ jest cyklem hamiltona, a jeśli tak to zwrócimy $TAK$(to znaczy nasz algorytm będzie akceptować parę ($x$, $y$)). 
Łatwo zauważyć że czas działania algorymtu jest ograniczony przez $O(|V| + |E|)$.
\\
\\ \noindent
Dowód $\Rightarrow$ \\ \noindent
Niech $x$ będzie grafem zawierającym cykl Hamiltona. 
Wówczas naszym $y$ bedzie właśnie ten cykl. 
Wtedy $|y|$ jest ograniczona przez $O(|V| + |E|)$ oraz zgodnie z opisem działania naszego algorytmu, $A$ zaakceptuje $(x, y)$. 
\\ \noindent
Dowód w drugą stronę jest równie prosty, więc go pominiemy.
\end{proof}

\noindent
Zauważmy że podpowiedź nie zawsze jest potrzebna. 
Np. w przypadku problemu polegającym na sprawdzeniu czy liczba jest podzielna przez $2$, możemy wziąć jakąkolwiek podowiedź, zignorować ją a następnie udzielić odpowiedzi w czasie wielomianowym. O takich problemach mówimy że są klasy $P$. 
\\
\\ \noindent

\begin{definition}[Redukcje wielomianowe]
Mówimy że problem $L$ jest wielomianowo redukowalny do problemu $Q$ jeśli:
\begin{enumerate}
\item $\exists f \forall x \quad  x \in L \Rightarrow f(x) \in Q$
\item Istnieje wielomianowy algorytm obliczający funkcję $f$
\end{enumerate}
\end{definition}
\noindent
Mimo że na pierwszy rzut oka może się to wydać niezrozumiałe, sens intuicyjny jest bardzo prosty. 
Chcielibyśmy "przetłumaczyć" problem $L$ na problem $Q$, to znaczy użyć rozwiązania problemu $Q$ tak abyśmy mogli za jego pomocą rozwiązać problem $L$. 
Jeśli uda nam się znaleźć taką funkcję(o której myślimy jak o algorytmie) to znaczy że znaleźliśmy redukcję problemu $L$ do problemu $Q$. 
Aby redukcja była wielomianowa, musi być spełniony drugi warunek, tzn. musimy umieć obliczyć tę funkcję w czasie wielomianowym.
% TODO pokazać jakiś przykład redukcji

\begin{definition}[Problem $NP$-zupełny]
Problem $L$ jest problemem $NP$-zupełnym jeśli:
\begin{enumerate}
\item $L \in NP$
\item Każdy problem z klasy $NP$ jest wielomianowo redukowalny do $L$
\end{enumerate}
\end{definition}
\noindent
O ile udowodnienie pierwszego warunku nie wydaje się specjalnie trudne(już raz to zrobiliśmy), tak drugi warunek może już sprawiać kłopoty. 
Zazwyczaj jednak nie dowodzi się tego bezpośrednio. 
Zamiast tego korzysta się z następującego faktu:
\begin{lemma}
Jeśli $L$, jest problemem $NP$, $Q$ jest problemem $NP$-zupełnym oraz $L$ jest redukowalny wielomianowo do $Q$ to $L$ jest problemem $NP$-zupełnym
\end{lemma}
\begin{proof}
Weźmy dowolny problem $A \in NP$, zredukujmy go do $Q$ a następnie do $L$. Czas obliczeń jest wówczas ograniczony przez sumę wielomianów, a więc przez wielomian.
\end{proof}
\noindent
Jednak aby skorzystać z tego lematu trzeba najpierw znaleźć problem który jest $NP$-zupełny. 
Jednym z pierwszych takich problemów którego $NP$-zupełność udowodniono był problem $SAT$(spełnialność formuł logicznych), a jak się później okazało, 
wiele innych problemów możana do niego zredukować. 
My zostawimy to bez dowodu. 
\\ 
\\ \noindent
To czy $P = NP$ jest wciąż otwartym, problemem milenijnym, którego rozwiązanie jest warte 1 000 000\$. 
Mimo że nikomu jeszcze nie udało się tego udowodnić, cały(duża większość) świat informatyki/matematyki wierzy że $P \neq NP$. 
Wiara jest na tyle mocna że wydawane są prace naukowe oraz dowodzone są twierdzenia przy założeniu że $P \neq NP$.
\\ 
\\ \noindent
O problemach $NP$-zupełnych można myśleć jak o takich problemach które są co najmniej tak samo trudne jak wszystkie inne problemy z klasy $NP$. 
Ogólnie rzecz biorąc, są to problemy bardzo trudne obliczeniowo, dla których nie istnieje żaden algorytm wielomianowy rozwiązujący je, co więcej prawdopodobnie nigdy nie będzie istniał, no chyba że $P = NP$.
Morał z tego jest taki, że jeśli wiemy że dany problem jest $NP$-zupełny, to raczej nie warto tracić czasu na rozwiązywanie go.
\\ 
\\ \noindent
Jako dodatek, poniżej prezentujemy liste najbardziej znanych problemów $NP$-zupełnych(lub $NP$-trudnych):
\begin{enumerate}
\item Problem SAT
\item Problem cyklu Hamiltona
\item Problem trójkolorowalności grafu
\item Problem komiwojażera($NP$-trudny)
\item Problem kliki
\item Problem plecakowy($NP$-trudny)
\item Problem sumy podzbioru
\item Problem minimalnego pokrycia zbioru($NP$-trudny)
\end{enumerate}

 
% TODO dodać coś o problemach NP-trudnych, może dodać jakieś obrazki
\noindent