<commit_before>%% -*- coding:utf-8 -*-
\section{Классы сложности $P$, $NP$}

При решении той или иной задачи возникают прежде всего два
вопроса. Имеет ли поставленная задача решение в принципе, т. е. может ли быть
построен алгоритм решающий поставленную задачу. Как только найден
положительный ответ на первый вопрос, т. е. построен алгоритм решающий
задачу, то следующей проблемой встает вопрос о практической
реализуемости предложенного решения. Здесь нам поможет теория
сложности алгоритмов которая решает вопрос о реализуемости тех или
иных алгоритмов. 

В следующей таблице \cite{bSchneier} 
% стр. 34
приведены некоторые большие числа
которые полезны при анализе сложности алгоритмов
\begin{table}
\centering
\begin{tabular}{|p {10cm}|p {5cm}|}
\hline
Физический аналог & Число \\ \hline
Вероятность быть убитым молнией (в течение дня) &
1 из 9 миллиардов ($2^{33}$) \\ 
Вероятность выиграть главный приз в государственной лотерее США &
1 из 4000000 ($2^{22}$) \\
Вероятность выиграть главный приз в государственной лотерее США и быть
убитым молнией в течение того же дня &
1 из $2^{61}$ \\
Вероятность утонуть (в США в течение года) &
1 из 59000 ($2^{16}$) \\
Вероятность погибнуть в автокатастрофе (в США в году) &
1 из 6100 ($2^{13}$) \\
Вероятность погибнуть в автокатастрофе (в США в течение времени жизни) &
1 из 88 ($2^7$) \\
Время до следующего оледенения &
14000 ($2^{14}$) лет \\
Время до превращения Солнца в сверхновую звезду &
$10^9$ ($2^{30}$) лет \\
Возраст планеты &
$10^9$ ($2^{30}$) лет \\
Возраст Вселенной & 
$10^{10}$ ($2^{34}$) лет \\
Число атомов планеты &
$10^{51}$ ($2^{170}$) \\
Число атомов Солнца &
$10^{57}$ ($2^{190}$) \\
Число атомов галактики & 
$10^{67}$ ($2^{223}$) \\
Число атомов Вселенной &
$10^{77}$ ($2^{265}$) \\
Объем Вселенной &
$10^{84}$ ($2^{280}$) $\mbox{см}^3$ \\
\hline
\multicolumn{2}{|l|}{Если Вселенная конечна:} \\
\hline
Полное время жизни вселенной &
$10^{11}$ ($2^{37}$) лет \\
& $10^{18}$ ($2^{61}$) секунд \\
\hline
\multicolumn{2}{|l|}{Если Вселенная бесконечна:} \\
\hline
Время до остывания легких звезд &
$10^{14}$ ($2^{47}$) лет \\
Время до отрыва планет от звезд &
$10^{15}$ ($2^{50}$) лет \\
Время до отрыва звезд от галактик & 
$10^{19}$ ($2^{64}$) лет \\
Время до разрушения орбит гравитационной радиацией &
$10^{20}$ ($2^{67}$) лет \\
Время до разрушения черных дыр процессами Хокинга &
$10^{64}$ ($2^{213}$) лет \\
Время до превращения материи в жидкость при нулевой температуре &
$10^{65}$ ($2^{216}$) лет \\
\hline
\end{tabular}
\caption{Большие числа \cite{bSchneier}}
\label{tblBigNumber}
\end{table}

\begin{example}
\emph{Факторизация целых чисел методом перебора}
\label{exAddAlgoTrialDivision}
Допустим что перед нами стоит задача о факторизации целого числа $x$. В
двоичном представлении $x$ состоит из $N$ знаков, т. е. 
$2^N \le x < 2^{N+1}$. В простейшем варианте (перебор делителей) мы
можем перебирать все целые числа от 2 до $2^{\frac{N}{2}}$ и для
каждого из таким чисел $2 < y \le 2^{\frac{N}{2}}$ искать остаток от
деления $x$ на $y$. Если $x$ делится на $y$ то задача решена и $y$
объявляется делителем числа $x$. Если ни одно из чисел $y$ не делит
$x$, то $x$ объявляется простым.
Т. о. исходная задача бьется на $2^{\frac{N}{2}}$ подзадач об отыскании
остатка от деления.

Допустим что в числе $x$ 20 знаков, т. е. $N=20$. В этом случае
необходимо выполнить $2^{10} = 1024$ операций деления чтобы найти
решение исходной задачи, что может быть легко сделано на простых
компьютерах. 

Вместе с тем если увеличить число знаков в 30 раз - $N=600$, то для
решения поставленной задачи необходимы выполнить $2^{300}$ операций
деления. Если посмотреть на табл. \ref{tblBigNumber}, то можно увидеть
что это число много больше числа атомов во вселенной
$2^{265}$. Т. е. даже если каждый атом вселенной будет представлять
собой некоторое простейшее вычислительное устройство, которое
вычисляет остаток от деления двух целых чисел, то использовав все
атомы вселенной невозможно будет решить поставленную задачу. 

Т. о. несмотря на присутствие простого алгоритма, задача факторизации
целых чисел, посредством этого алгоритма, становится практически
не реализуемой для чисел длиной $600$ символов в двоичной записи
несмотря на то, что число $600$ кажется не очень большим по сравнению
с $20$ (где задача является практически реализуемой).
\end{example}


\subsection{Иерархия классов сложности}

Ниже даются формальные определения для задач которые являются
практически реализуемыми $P$. Также определяется класс задач которые
являются практически не реализуемыми (до тех пор пока не доказано, что
$P = NP$).

\begin{definition}[Размер задачи]
Размером задачи $N$ мы будем называть число символов алфавита машины
Тьюринга, содержащихся на ленте в исходном состоянии, т. е. другими
словами размером задачи мы будем считать длину строки которая
поступает на вход машины Тьюринга.
\end{definition}

Например в примере \ref{exAddAlgoTrialDivision} размером задачи
является длина числа $x$ (для которого ищутся делители) в двоичной
записи. 

\begin{definition}[Класс $P$]
Задача (алгоритм) принадлежит к классу $P$ (Polynomial) если он может
быть решен за 
 $O\left(N^k\right)$ шагов на детерминированной машине Тьюринга.
Здесь $N$ - размер исходной задачи, $k$ - произвольное целое число,
которое не зависит от $N$.  
\end{definition}

Класс $P$ определяет класс задач которые являются практически
реализуемыми. Например задача о сортировке неупорядоченных данных
(списка) может быть решена за 
$O\left(N log N \right) = O\left(N^2\right)$ шагов, где $N$ - число
элементов в списке, который надо отсортировать (размер задачи).

\begin{definition}[Класс $NP$]
Задача (алгоритм) принадлежит к классу $NP$ (Nondetermenistic Polynomial )если
он может быть решен за  $O\left(N^k\right)$ шагов на
не детерминированной машине Тьюринга.  Здесь $N$ - размер исходной
задачи, $k$ - произвольное целое число, которое не зависит от $N$. 
\end{definition}

Одним из примеров $NP$ задачи является задача факторизации целых
чисел. Не детерминированная машина Тьюринга может угадать решение (за
один шаг) и проверить его (умножить два угаданных числа и сравнив
результат умножения с исходным числом) за полиномиальное время. Вместе
с тем вопрос о принадлежности задачи факторизации к классу $P$
является открытым. 

\input ./add/algo/figpnp.tex

Задача о равенстве классов $P$ и $NP$ является одной из важнейших
нерешенных задач математики и, наверное, важнейшей из нерешенных задач
теории алгоритмов. Для того чтобы показать каким образом $NP$ задача
может быть сведена к  $P$ необходимо ввести класс $NP$-полных задач,
которые являются, в некотором смысле, самыми сложными из $NP$ задач. 

\begin{definition}[Класс $NPC$ ($NP$-полный ($NP$-complete))]
Задача $M$ принадлежит к классу $NPC$, если любая $NP$ задача
может быть сведена к $M$.
\end{definition}

Таким образом если будет найден полиномиальный алгоритм хотя бы для
одной $NPC$ задачи, то будут найдены полиномиальные алгоритмы
для всех $NP$ задач (см. рис. \ref{figAddAlgoPNP}). 
 

\subsection{Теорема Кука-Левина}

\begin{theorem}
\emph{(Теорема Кука-Левина)}
Задача о выполнимости булевой формулы в КНФ\footnote{Конъюнктивная нормальная форма} (SAT) является NP полной
\label{theoremAddAlgoCookTheorem}
\end{theorem}

\begin{proof}
TBD
\end{proof}<commit_msg>Cook - Levin<commit_after>%% -*- coding:utf-8 -*-
\section{Классы сложности $P$, $NP$}

При решении той или иной задачи возникают прежде всего два
вопроса. Имеет ли поставленная задача решение в принципе, т. е. может ли быть
построен алгоритм решающий поставленную задачу. Как только найден
положительный ответ на первый вопрос, т. е. построен алгоритм решающий
задачу, то следующей проблемой встает вопрос о практической
реализуемости предложенного решения. Здесь нам поможет теория
сложности алгоритмов которая решает вопрос о реализуемости тех или
иных алгоритмов. 

В следующей таблице \cite{bSchneier} 
% стр. 34
приведены некоторые большие числа
которые полезны при анализе сложности алгоритмов
\begin{table}
\centering
\begin{tabular}{|p {10cm}|p {5cm}|}
\hline
Физический аналог & Число \\ \hline
Вероятность быть убитым молнией (в течение дня) &
1 из 9 миллиардов ($2^{33}$) \\ 
Вероятность выиграть главный приз в государственной лотерее США &
1 из 4000000 ($2^{22}$) \\
Вероятность выиграть главный приз в государственной лотерее США и быть
убитым молнией в течение того же дня &
1 из $2^{61}$ \\
Вероятность утонуть (в США в течение года) &
1 из 59000 ($2^{16}$) \\
Вероятность погибнуть в автокатастрофе (в США в году) &
1 из 6100 ($2^{13}$) \\
Вероятность погибнуть в автокатастрофе (в США в течение времени жизни) &
1 из 88 ($2^7$) \\
Время до следующего оледенения &
14000 ($2^{14}$) лет \\
Время до превращения Солнца в сверхновую звезду &
$10^9$ ($2^{30}$) лет \\
Возраст планеты &
$10^9$ ($2^{30}$) лет \\
Возраст Вселенной & 
$10^{10}$ ($2^{34}$) лет \\
Число атомов планеты &
$10^{51}$ ($2^{170}$) \\
Число атомов Солнца &
$10^{57}$ ($2^{190}$) \\
Число атомов галактики & 
$10^{67}$ ($2^{223}$) \\
Число атомов Вселенной &
$10^{77}$ ($2^{265}$) \\
Объем Вселенной &
$10^{84}$ ($2^{280}$) $\mbox{см}^3$ \\
\hline
\multicolumn{2}{|l|}{Если Вселенная конечна:} \\
\hline
Полное время жизни вселенной &
$10^{11}$ ($2^{37}$) лет \\
& $10^{18}$ ($2^{61}$) секунд \\
\hline
\multicolumn{2}{|l|}{Если Вселенная бесконечна:} \\
\hline
Время до остывания легких звезд &
$10^{14}$ ($2^{47}$) лет \\
Время до отрыва планет от звезд &
$10^{15}$ ($2^{50}$) лет \\
Время до отрыва звезд от галактик & 
$10^{19}$ ($2^{64}$) лет \\
Время до разрушения орбит гравитационной радиацией &
$10^{20}$ ($2^{67}$) лет \\
Время до разрушения черных дыр процессами Хокинга &
$10^{64}$ ($2^{213}$) лет \\
Время до превращения материи в жидкость при нулевой температуре &
$10^{65}$ ($2^{216}$) лет \\
\hline
\end{tabular}
\caption{Большие числа \cite{bSchneier}}
\label{tblBigNumber}
\end{table}

\begin{example}
\emph{Факторизация целых чисел методом перебора}
\label{exAddAlgoTrialDivision}
Допустим что перед нами стоит задача о факторизации целого числа $x$. В
двоичном представлении $x$ состоит из $N$ знаков, т. е. 
$2^N \le x < 2^{N+1}$. В простейшем варианте (перебор делителей) мы
можем перебирать все целые числа от 2 до $2^{\frac{N}{2}}$ и для
каждого из таким чисел $2 < y \le 2^{\frac{N}{2}}$ искать остаток от
деления $x$ на $y$. Если $x$ делится на $y$ то задача решена и $y$
объявляется делителем числа $x$. Если ни одно из чисел $y$ не делит
$x$, то $x$ объявляется простым.
Т. о. исходная задача бьется на $2^{\frac{N}{2}}$ подзадач об отыскании
остатка от деления.

Допустим что в числе $x$ 20 знаков, т. е. $N=20$. В этом случае
необходимо выполнить $2^{10} = 1024$ операций деления чтобы найти
решение исходной задачи, что может быть легко сделано на простых
компьютерах. 

Вместе с тем если увеличить число знаков в 30 раз - $N=600$, то для
решения поставленной задачи необходимы выполнить $2^{300}$ операций
деления. Если посмотреть на табл. \ref{tblBigNumber}, то можно увидеть
что это число много больше числа атомов во вселенной
$2^{265}$. Т. е. даже если каждый атом вселенной будет представлять
собой некоторое простейшее вычислительное устройство, которое
вычисляет остаток от деления двух целых чисел, то использовав все
атомы вселенной невозможно будет решить поставленную задачу. 

Т. о. несмотря на присутствие простого алгоритма, задача факторизации
целых чисел, посредством этого алгоритма, становится практически
не реализуемой для чисел длиной $600$ символов в двоичной записи
несмотря на то, что число $600$ кажется не очень большим по сравнению
с $20$ (где задача является практически реализуемой).
\end{example}


\subsection{Иерархия классов сложности}

Ниже даются формальные определения для задач которые являются
практически реализуемыми $P$. Также определяется класс задач которые
являются практически не реализуемыми (до тех пор пока не доказано, что
$P = NP$).

\begin{definition}[Размер задачи]
Размером задачи $N$ мы будем называть число символов алфавита машины
Тьюринга, содержащихся на ленте в исходном состоянии, т. е. другими
словами размером задачи мы будем считать длину строки которая
поступает на вход машины Тьюринга.
\end{definition}

Например в примере \ref{exAddAlgoTrialDivision} размером задачи
является длина числа $x$ (для которого ищутся делители) в двоичной
записи. 

\begin{definition}[Класс $P$]
Задача (алгоритм) принадлежит к классу $P$ (Polynomial) если он может
быть решен за 
 $O\left(N^k\right)$ шагов на детерминированной машине Тьюринга.
Здесь $N$ - размер исходной задачи, $k$ - произвольное целое число,
которое не зависит от $N$.  
\end{definition}

Класс $P$ определяет класс задач которые являются практически
реализуемыми. Например задача о сортировке неупорядоченных данных
(списка) может быть решена за 
$O\left(N log N \right) = O\left(N^2\right)$ шагов, где $N$ - число
элементов в списке, который надо отсортировать (размер задачи).

\begin{definition}[Класс $NP$]
Задача (алгоритм) принадлежит к классу $NP$ (Nondetermenistic Polynomial )если
он может быть решен за  $O\left(N^k\right)$ шагов на
не детерминированной машине Тьюринга.  Здесь $N$ - размер исходной
задачи, $k$ - произвольное целое число, которое не зависит от $N$. 
\end{definition}

Одним из примеров $NP$ задачи является задача факторизации целых
чисел. Не детерминированная машина Тьюринга может угадать решение (за
один шаг) и проверить его (умножить два угаданных числа и сравнив
результат умножения с исходным числом) за полиномиальное время. Вместе
с тем вопрос о принадлежности задачи факторизации к классу $P$
является открытым. 

\input ./add/algo/figpnp.tex

Задача о равенстве классов $P$ и $NP$ является одной из важнейших
нерешенных задач математики и, наверное, важнейшей из нерешенных задач
теории алгоритмов. Для того чтобы показать каким образом $NP$ задача
может быть сведена к  $P$ необходимо ввести класс $NP$-полных задач,
которые являются, в некотором смысле, самыми сложными из $NP$ задач. 

\begin{definition}[Класс $NPC$ ($NP$-полный ($NP$-complete))]
Задача $M$ принадлежит к классу $NPC$, если любая $NP$ задача
может быть сведена к $M$.
\end{definition}

Таким образом если будет найден полиномиальный алгоритм хотя бы для
одной $NPC$ задачи, то будут найдены полиномиальные алгоритмы
для всех $NP$ задач (см. рис. \ref{figAddAlgoPNP}). 
 

\subsection{Теорема Кука-Левина}

Как только мы ввели класс сложности $NPC$ встает вопрос о задачах
которые в него входят. Ниже будет показано, что задача о выполнимости
булевой формулы в конъюнктивной нормальной форме является $NP$ полной. 

\begin{definition}[КНФ - Конъюнктивная нормальная форма (SAT)]
TBD
\end{definition}

\begin{theorem}
\emph{(Теорема Кука-Левина)}
Задача о выполнимости булевой формулы в КНФ является NP полной,
т. е. принадлежит классу $NPC$.
\label{theoremAddAlgoCookTheorem}
\end{theorem}

\begin{proof}
TBD
\end{proof}
{'fraction_non_alphanumeric': 0.11029560298969766, 'fraction_numerical': 0.02962763450272709, 'mean_word_length': 4.910067648229208, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2534756', 'n_tokens_mistral': 6606, 'n_tokens_neox': 7557, 'n_words': 1912}