\Section{Классы сложности}{24 мая}{Олег Свидченко}

\Subsection{Типы задач}

Пусть $X$ --- множество всех конечных строк. Тогда задачи делятся на два типа:\\
\begin{MyList}
    \item \t{Поиск (Search Problem)}\\
    $X \mapsto Y$
    \item \t{Распознавание (Decision Problem)}\\
    $X \mapsto \{0, 1\}$
\end{MyList}
Займемся решением задачи распознавания, т.к. очевидно, что через нее можно выразить задачу поиска.\\

\Subsection{Классы сложности задач}
\begin{MyList}
    \item \t{P}\\
    $\exists$ полиномиальное решение задачи, т.е. алгоритм, проверяющий, лежит ли строка $s$ в множестве всех строк $L$, для которых ответ на задачу $1$ \\
    \item \t{NP}\\
    Есть два равноправных определения. Первое --- историческое, второе --- практическое.\\
    \begin{MyList}
        \item
        Деревом возможностей работы алгоритма назовем дерево конечной глубины, каждый узел (кроме листьев) которого соответствует случайному выбору поддерева дальнейших вычислений, а ребра и листья являются детерминированными полиномиальными алгоритмами.\\ 
        Естественно, не утверждается, что у любого алгоритма существует такое дерево, но очевидно, что любому такому дереву соответствует алгоритм.\\
        Задача лежит в классе \t{NP} если существует дерево возможностей работы алгоритма (и, соответственно, алгоритм $A$) такое, что $s \in L \Leftrightarrow \exists$ ветка вычислений такая, что $A(s) = 1$.
        \item
        Задача лежит в классе \t{NP} если существует полиномиальный алгоритм $R(x, y): x \in L \Leftrightarrow \exists y: |y| = poly(|x|) \wedge R(x, y) = 1$
    \end{MyList}
    Из второго определения первое следует очевидным образом (просто угадываем $y$), а обратное следствие так же очевидно ($y$ --- последовательность выборов, $|y|$ точно меньше глубины дерева)\\
\end{MyList}

\Subsection{Сравнение задач}

$A \leq B$ (Задача $A$ сводится к задаче $B$) если $\exists f \in \t{poly}: \forall x A(x) = B(f(x))$\\
Очевидно, что это отношение эквивалентности.\\
Типы сведений:\\
\begin{MyList}
    \item \t{poly} (По Карпу; Рассмотрено выше)
    \item \t{many --- one} (По Карпу; Решив задачу $B$ можем решить сразу много задач $A$)
    \item \t{many --- many} (По Куку)\\
    Алгоритм $A$ имеет оракула $L$, если может за время $\O(1)$ решить задачу $L$. (Обозначается $A^{L}$)\\
    $L_{1} \leq L_{2}$ если $\exists A^{L_{2}} \in \t{poly}: A^{L_{2}}(s) = L_{1}(s)$
\end{MyList}
\begin{Lm}
    $L_{1} \leq L_{2}, L_{2} \in \t{NP/P} \Rightarrow L_{1} \in \t{NP/P}$
    \begin{proof}
        Очевидно: сведем $L_{1}$ к $L_{2}$ и решим.
    \end{proof}
\end{Lm}

\Subsection{Классы сложности задач (продолжение)}
\begin{MyList}
    \item \t{NP-hard}\\
    $A \in \t{NP-hard} \Leftrightarrow \forall L \in \t{NP}: L \leq A$
    \item \t{NP-complete}\\
    $\t{NP-complete} = \t{NP} \cap \t{NP-hard}$
\end{MyList}
\begin{Lm}
    $L_{1} \leq L_{2}, L_{1} \in \t{NP-complete} \Rightarrow L_{2} \in \t{NP-hard}$
    \begin{proof}
        $\forall A \in \t{NP}: A \leq L_{1} \leq L_{2} \Rightarrow A \leq L_{2}$
    \end{proof}
\end{Lm}