From 660a71ef15d6a826408f44bfe2186e9ff1b07aa3 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 29 May 2022 12:01:52 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=B8=D0=B5?= =?UTF-8?q?=204=20=D0=B8=205=20=D0=BB=D0=B0=D0=B1=D0=BE=D1=80=D0=B0=D1=82?= =?UTF-8?q?=D0=BE=D1=80=D0=BD=D1=8B=D1=85?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- reports/lab4/lab4.tex | 120 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 120 insertions(+) create mode 100644 reports/lab4/lab4.tex (limited to 'reports/lab4/lab4.tex') diff --git a/reports/lab4/lab4.tex b/reports/lab4/lab4.tex new file mode 100644 index 0000000..b4d2a4a --- /dev/null +++ b/reports/lab4/lab4.tex @@ -0,0 +1,120 @@ +\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} -- cgit v1.2.3