\documentclass[spec, och, labwork]{SCWorks}
\usepackage{preamble}

\begin{document}
\include{titlepage.tex}

\begin{definition}
    NP-полная задача "--- в теории алгоритмов задача с ответом <<да>> или
    <<нет>> из класса NP, к которой можно свести любую другую задачу из этого
    класса за полиномиальное время (то есть при помощи операций, число которых
    не превышает некоторого полинома в зависимости от размера исходных данных).
    Таким образом, NP-полные задачи образуют в некотором смысле подмножество
    <<типовых>> задач в классе NP: если для какой-то из них найден
    <<полиномиально быстрый>> алгоритм решения, то и любая другая задача из
    класса NP может быть решена так же <<быстро>>.
\end{definition}

\begin{definition}
    Алфавитом называется всякое конечное множество символов (например, $\{0,
    1\}$ или $\{a, b, c\}$). Множество всех возможных слов (конечных строк,
    составленных из символов этого алфавита) над некоторым алфавитом $\Sigma$
    обозначается $\Sigma_*$. Языком $L$ над алфавитом $\Sigma$ называется всякое
    подмножество множества $\Sigma_*$, то есть $L \subset \Sigma_*$.
\end{definition}

\begin{definition}
    Пусть $L_1$ и $L_2$ "--- два языка над алфавитом $\Sigma$. Язык $L_1$
    называется сводимым (по Карпу) к языку $L_2$, если существует функция, $f :
    \Sigma_* \to \Sigma_*$, вычислимая за полиномиальное время, обладающая
    следующим свойством: $x \in L_1$ тогда и только тогда, когда $f(x) \in L_2$.
    Сводимость по Карпу обозначается как $L_1 \leq_p L_2$ или $L_1 \propto L_2$.
\end{definition}

\begin{definition}
    Язык $L_2$ называется NP-трудным, если любой язык из класса NP сводится к
    нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в
    классе NP.
\end{definition}

Неформально говоря, то что задача A сводится к задаче B, означает, что задача A
«не сложнее» задачи B (так как, если мы можем решить B, то можем решить и A.
Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи,
которые <<сложнее>> их (то есть те задачи, к которым могут быть сведены
NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче»
их (то есть те задачи, которые сводятся к NP-полным задачам).

Из определения следует, что, если будет найден алгоритм, решающий некоторую
(любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в
классе P, то есть будут решаться за полиномиальное время.

\begin{definition}
    Тавтологией называется булева формула, принимающая значение 1 на всех
    наборах значений её переменных.
\end{definition}

Теорема Кука "--- Левина (также просто теорема Кука) утверждает, что задача о
выполнимости булевой формулы в КНФ (ВЫП) является NP-полной.

Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной
работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных
задач. Независимо в то же время эта теорема была доказана советским математиком
Леонидом Левиным.

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к
ВЫП. С. Кук (S. Cook) определил класс NP задач распознавания свойств следующим
образом. Задача принадлежит классу NP, если:
\begin{enumerate}
    \item
        решением задачи является один из двух ответов: <<да>> или <<нет>>
        (задача распознавания свойств);
    \item
        требуемый ответ может быть получен на недетерминированном вычислительном
        устройстве за полиномиальное время.
\end{enumerate}

Этот класс, как позже показал Р. Карп (R. Karp) в свою очередь содержит в себе
другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые
в пределах этого класса одна к другой.

После появления результатов Кука была доказана NP-полнота для множества других
задач. При этом чаще всего для доказательства NP-полноты некоторой задачи
приводится полиномиальное сведение задачи ВЫП к данной задаче, возможно в
несколько шагов, то есть с использованием нескольких промежуточных задач.

\begin{theorem}
    ВЫП "--- язык булевых формул из $n$ переменных, для которых существует
    подстановка, при которой формула истинна.

    \begin{equation*}
        \text{ВЫП} = \{ \varphi ~ | ~ \exists ~ x : \varphi(x) = 1 \}
    \end{equation*}
\end{theorem}
\begin{proof}
    $\text{ВЫП} \in \text{NP}$, потому что можно написать недетерминированную
    программу $p$, которая распознает язык ВЫП. Она будет недетерминированно
    выбирать подстановку, проверять, истинна ли формула при такой подстановке, и
    выдавать ответ.
\end{proof}

Сведения задачи ВЫП к задаче NP-полноты языка, состоящего из булевых функций, не
являющихся тавтологиями можно добиться с помощью вычислимой полиномиальной
функции.

Допустим, с помощью некоторой функции $\varphi(x_1, \dots, x_n, \dots)$ можно
получить кортеж $(0, 1, 1, 1, \dots)$. Зададим функцию $\nu(x_1, \dots, x_n,
\dots)$, что для такого входа мы будем получать все кортежи вида $(1, 0, 0, 0,
\dots)$, $(0, 1, 0, 0, \dots)$ и т.д.

Для кортежей с большим количеством нулей, функция $\nu$ задаётся аналогичным
образом.

Получаем, что задача имеет сложность
\begin{equation*}
    \sum_{i = 0}^\infty C_n^i \cdot \sum_{i = 0}^\infty C_n^{n - i} =
    \sum_{i = 0}^\infty C_n^i \cdot C_n^{n - i} =
    \sum_{i = 0}^\infty (C_n^i)^2
\end{equation*}
где $C_n^k$ "--- биномиальный коэффициент.

\end{document}