1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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}
|
