\Section{Классы сложности}{24 мая}{Зуев Михаил}

\Subsection{Примеры задач из разных классов}\\

Немного истории. Концепция NP-полноты развивалась в 1960х-1970х годах независимо в СССР и CША (Эдмондс, Левин, Яблонский). В 1971 году Стивен Кук сформулировал гипотезу о P vs. NP. \\

\Subsubsection{SAT}\\

{\bf Задача:} Проверить выполнимость данной формулы.\\

Левин и Кук независимо доказали NP-полноту задачи SAT, которая стала универсальной для доказательства NP-полноты многих других задач.\\
У выполнимой формулы существует выполняющий набор. Он будет являтся сертификатом. Очевидно, существует полимиальный алгоритм, который подставляет значения набора и проверяет, выполнилась ли формула. Значит, $SAT \in NP$\\
Доказательство $SAT \in NP-hard$ не было дано (да и это не нужно). В общих словах, оно заключается на написании формулы на ячейках памяти и состоянии машины Тьюринга, при выолнении которых машина даст ответ 1.\\

\Subsubsection{CNFSAT}\\

{\bf Задача:} Проверить выполнимость формулы, заданной в КНФ.\\

$CNFSAT \in NP$ -- аналогично SAT.\\
Рассмотрим дерево расщипления по данной формуле. По этому дереву с помощью добавления новых переменных можно построить формулу в КНФ (подробно это было на курсе ДМ). Размер этой формулы будет полимиален относительной исходной. Т.к. $SAT \in NP-hard$, а мы свели $SAT$ к $CNFSAT$, то $CNFSAT \in NP-hard$.\\

\Subsubsection{3-CNFSAT}\\

{\it Комментарий:} Я не уверен, что это было на лекции.\\

{\bf Задача:} Проверить выполнимость формулы, заданной в 3-КНФ.\\

Рассмотрим формулу в КНФ. Путь в некотором ее дизъюнкте $k$ переменных.
\begin{enumerate}
	\item
	Если $k < 3$, то продублируем некоторую переменную из дизъюнкта, чтобы получить 3 переменных в дизънкте.
	\item
	Если $k > 3$. Назовем их $x_1, x_2,\ldots,x_k$. Добавим новые переменные $z_1, z_2,\ldots,z_{k - 2}$. Рассмотрим формулу:\\
	\[
	(x_1 \vee x_2 \vee z_1) \wedge (x_3 \vee \neg z_1 \vee z_2) \wedge \ldots \wedge (x_i \vee \neg z_{i - 2} \vee z_{i - 1})\wedge \ldots \wedge (x_{k - 1} \vee x_k \vee \neg z_{k - 2})
	\]
\end{enumerate}

Пусть в выолняющем наборе исходной формулы некоторое $x_i = 1$. Тогда, в новой формуле мы можем расставить выполняющие значения в $z_i$ (сначала будем ставить от первой скобки до скобки с $x_i$, потом от последней; эти значения будут чередоваться, но это не важно, т.к. скобка с $x_i$ все равно выполнится).\\
Обратно, если все $x_i = 0$, то новая формула не может выполниться. Чтобы выполнилась 1-я скобка, $z_i = 1$. Для выполнения 2-й скобки $z_2 = 1$. Аналогично получаем $z_i = 1$. Но тогда не выполнится последняя скобка.\\
Получаем, что новая формула равносильна исходной, а значит мы свели $CNFSAT$ к $3-CNFSAT \Rightarrow 3-CNFSAT \in NP-hard$\\

Отсюда можно доказать $k-CNFSAT \in NP-complete$ для любого $k > 2$.

\Subsubsection{Independent set}\\

{\bf Задача:} В данном неор. графе проверить наличие независимого множества размера $k$.\\

Для множества вершин за $O(poly)$ можно проверить его независимость $\Rightarrow IND \in NP$.\\

Сведем к $IND$ задачу $3-CNFSAT$. Пусть в формуле $k$ дизъюнктов. Создадим для каждого дизъюнкта 3 вершины, соединим их ребрами. Также соединим ребрами все пары вершины, которые соответствуют переменной и ее отрицанию.\\
Если для данной формулы существует выполняющий набор, но существует независимое множество размера $k$. В каждом дизъюнкте возмем по 1 вершине, переменная которой равна 1. Т.к. у нас не будет взята вершины из пар переменная-ее отрицание, то мы получили независимое множество.\\
В обратную сторону, если мы нашли независимое множество размера $k$, то в нем есть по 1 вершине для каждого дизъюнкта. Переменная и ее отрицания не могут быть одновременно в этом множестве, а значит мы получили корректный выполняющий набор.\\

Вершинное покрытие сводится к независимому множеству, а значит тоже лежит в $NP-comlete$. Аналогично в $NP-comlete$ лежит задача о клике.

\Subsubsection{Halting problem}\\

{\bf Задача:} По данному алгоритму и входным данным проверить, завершится ли когда-нибудь его выполнение.\\

Эта задача лежит в классе $NP-hard$, но не лежит в $NP$.\\
Задача из $NP$ сводится к $Halting problem$ записыванием алгоритма-перебора строк-сертификатов и запуска проверки, что этот сертификат подходит. Если данная программа завершится, то будет найдет сертификат.\\

\Subsubsection{Другие задачи}

Задача изоморфизма графов является $NP$, но неизвестно, принадлежит ли она $NP-hard$. Также к $NP$ относятся задача факторизации. Рюкзак является $NP-comlete$ задачей.