 \documentclass[12pt, leqno]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{algorithm2e}

\usepackage{tabto} %Табуляция
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{indentfirst}  % абзацный отступ после заголовка
\usepackage{enumitem} %Item tricks


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}
\theoremstyle{definition}
\newtheorem{Example}{Пример}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\let\yield\Rightarrow
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\PP{{\mathsf{P}}}
\def\NP{{\mathsf{NP}}}
\def\NPc{{\mathsf{NP}}\text{-}{\rm c}}
\def\coNP{{\rm co}\text{-}{\mathsf{NP}}}
\def\DTIME{{\mathsf{DTIME}}}
\def\NTIME{{\mathsf{NTIME}}}
\def\HALT{{\rm{HALT}}}
\def\SAT{{\rm{SAT}}}
\def\3SAT{{\rm{3\text{-}SAT}}}
\def\2SAT{{\rm{2\text{-}SAT}}}
\def\UNSAT{{\rm{UNSAT}}}
\def\LL{{\mathrm{LL}}}
\def\poly{{\rm{poly}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem^*}\negmedspace .$  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem}^{\dagger}$.  }\setcounter{subproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}

\begin{document}
\centerline{\LARGE Задание 4}

\medskip

\begin{center}
	{\Large Сложность вычислений: классы $\PP$, $\NP$ и $\coNP$ }
\end{center}

\bigskip

{\bf Литература: }
\begin{enumerate}

\item Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. \\ {\it Алгоритмы. Построение и анализ. }\\  2-е изд. М.: Вильямс, 2005.

\item Sipser M. \\ {\it Introduction to the theory of computation}

\item Hopcroft J., Ullman J.\\ {\it Introduction to Automata Theory, Languages, and Computation.}\\ 1-st edition, 1979.

\end{enumerate}

\section{Недетерминированные машины Тьюринга}


Определение недетерминированной машины Тьюринга получается из определения детерминированной подобно тому как из определения ДКА получается определение НКА: достаточно заменить функцию переходов на отношение переходов и добавить  квантор существования в условие приёма слова. То есть, недетеринированная машина Тьюринга $M$ принимает слово $x$, если существует последовательность переходов, которая приводит машину $M$ на слове $x$ в принимающее состояние. 


\bigskip

\upr Покажите, что детереминированные и недетерминированные машины Тьюринга распознают один и тот же класс языков. 

\bigskip

Если недетерминированная машина Тьюринга $M$ распознаёт язык $L$, причём для каждого слова $x$ из $L$ она делает не более чем $O(n^c)$ тактов, то язык $L$ лежит в классе $\NTIME(O(n^c))$. Такую машину Тьюринга мы будем называть недетерминированной полиномиальной.

Таким образом, аналогично определению класса $\PP$, получим определение класса $\NP$:

$$
 \NP = \bigcup_{c \geq 0} \NTIME(O(n^c))
$$


\section{Класс $\NP$}

Приведём более наглядное эквивалентное определение класса $\NP$. Под записью $M(x,y)$ мы понимаем, что на вход 
машине $M$ подали строки $x$ и $y$, записанные через разделитель, например $M(x,y) = M(x\#y)$.

Напомним, что в случае когда мы рассматриваем соответствующую машине Тьюринга $M$ вычислимую функцию $M(\cdot)$ одного аргумента, запись $M(x) = 1$ означает, что машина $M$ принимает слово $x$ или что то же самое, что слово $x$ принадлежит языку, распознаваемому машиной $M$: $x \in L(M)$.

\begin{Def}
	Язык $L$ лежит в классе $\NP$, если существуют полином $p(n) : \NN \to \NN$ и (детерминированная) полиномиальная МТ $M$, такие что
	\begin{align*}
	 x \in L\Leftrightarrow \exists y \in \Sigma^{p(|x|)}\ M(x,y) = 1.
	\end{align*}
	Слово $y$ мы будем называть \emph{сертификатом} для слова $x$. 
\end{Def}

\upr Покажите, что два определения класса $\NP$ эквивалентны.

\prp Пусть мы не накладываем полиномиального ограничения на сертификат, но при этом машина $M$ является полиномиальной по длине входного слова $x$.
 

То есть, для языка $L$ есть машина $M(x,y)$ полиномиальная по длине входа $|x|$ и 
\begin{align*}
 x \in L\Leftrightarrow \exists y \in \Sigma^*\ M(x,y) = 1.
\end{align*}
Верно ли, что $L \in \NP$? Если да, то как найти полиномиальный по $x$ сертификат $y$?



\section{Сводимости}

Довольно часто в сложности вычислений мы сталкиваемся со следующей ситуацией: оказывается, что мы умеем решать задачу $A$, если мы уже умеем решать задачу $B$. Или наоборот, задача $B$ является сложной (или даже неразрешимой), если задача $A$ является сложной (неразрешимой).

Для описания таких отношений между языками мы пользуемся сводимостью. В этом задании мы будем говорить об $m$-сводимости или сводимости по Карпу.


\begin{Def}
	Пусть для языка $A \subseteq \Sigma_1^*$ существует такая вычислимая функция $f : \Sigma_1^* \to \Sigma_2^*$, что слово $x$ принадлежит $A$ тогда и только тогда, когда слово $f(x)$ принадлежит языку $B$. Будем говорить, что язык $A$ сводится к языку $B$ $m$-сводимостью и обозначать это как $A \leq_m B $. В формулах это выглядит как
%		$$ x \in A \iff f(x) \in B. $$
	
\end{Def}



\begin{Def}
	Пусть для языка $A \subseteq \Sigma_1^*$ существует такая полиномиально-вычислимая функция $f : \Sigma_1^* \to \Sigma_2^*$, что слово $x$ принадлежит $A$ тогда и только тогда, когда слово $f(x)$ принадлежит языку $B$. Будем говорить, что язык $A$ сводится к языку $B$ полиномиальной $m$-сводимостью (сводимостью по Карпу) и обозначать это как $A \leq^p_m B $.
\end{Def} 

Для краткости, мы будем говорить вместо «сводится $m$-сводимостью» и «сводится полиномиальной $m$-сводимостью» «сводится» и «полиномиально сводится».

\upr Покажите, что если задача $\HALT$ сводится к задаче $A$, то задача $A$ является неразрешимой.

\upr Покажите, что если задача $A$ сводится полиномиально к задаче $B$ и задача $B$ лежит в классе $\PP$, то и задача $A$ лежит в классе $\PP$.

\bigskip

Задача $A$ является $\NP$-полной, если задача $A$ лежит в $\NP$ и любая задача $B \in \NP$ полиномиально сводится к $A$
Класс $\NP$-полных задач мы будем обозначать  $\NPc$. Формально

$$
 L \in \NPc \Leftrightarrow L \in \NP,\ \forall A \in \NP: A \leq^p_m L.
$$

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

Определение $\NP$-полного языка состоит из двух частей. Первую из них, о том, что любой язык из класса $\NP$ сводится к языку $A$ выделяют в отдельное определение -- такие языки называются $\NP$-трудными. Таким образом, язык $A$ является $\NP$-полным, если он является $\NP$-трудным и принадлежит классу $\NP$.


Помимо классов $\NP$ и $\NPc$ нас также будет интересовать класс $\coNP$, состоящий из языков, являющихся дополнением к языкам из $\NP$. То есть, если язык $L$ лежит в классе $\NP$, то язык $\bar L$ лежит в классе $\coNP$ 




	


\section{$\NP$-полные задачи}


Приведём пример $\NP$-полной задачи.

\begin{Example}
	Язык $\SAT$ состоит из всех выполнимых булевых формул $\phi$, заданных в конъюнктивной нормальной форме.
	$$
		\SAT = \{ \phi\,|\, \exists y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 1 \}
	$$
\end{Example}

\begin{known}[Кук, Левин]
	Язык $\SAT$ является $\NP$-полным.
\end{known}

\upr Изучить доказательство теоремы Кука-Левина. Ознакомиться с ним я рекомендую в книжке Сипсера.

На семинаре мы говорили о языке $\3SAT$, который состоит из выполнимых булевых формул, каждый дизъюнкт которых содержит ровно три переменных. Пример такой формулы:
$$ 
	\phi = (x_1\vee x_2 \vee \neg x_3) \wedge (\neg x_4 \vee x_5 \vee x_1).
$$

\prp Показать, что из теоремы Кука-Левина следует, что $\3SAT \in \NPc$

\prp Показать, что $\2SAT \in \PP$.

\bigskip

Также нам интересен класс $\coNP$, состоящий из языков, дополнение которых лежит в $\NP$.


Определим язык $\UNSAT$ как язык состоящий из невыполнимых булевых формул, заданных КНФ. То есть
$$
	\UNSAT = \{ \phi\,|\, \forall y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 0 \}
$$

\upr Показать, что язык $\UNSAT$ лежит в классе $\coNP$.


Полнота языка в классе относительно сводимостей осмыслена не только в случае $\NP$-полных языков. В учебных целях мы будем пользоваться полиномиальной $m$-сводимостью также в классе $\PP$ и $\coNP$.
Разумеется, полнота относительно полиномиальной сводимости в классе $\PP$ выглядит нелепо -- в реальной жизни класс $\PP$ исследуют относительно более осмысленной сводимости -- сводимости на логарифмической памяти. 
Относительно этой сводимости, например, полна задача о проверки пустоты языка, заданного КС-грамматикой. То есть, любая задача из класса $\PP$ сводится к задаче о пустоте языка, заданного КС-грамматикой на логарифмической памяти. Подробнее об этом можно почитать, например, в книжке Хопкрофта-Ульмана «Introduction to Automata Theory, Languages, and Computation» 1979-го года -- второе здание этой книги, выпущенное совместно с Мотвани многие из вас изучали в курсе ТРЯП, но второе издание сильно упрощено и сжато. 

\prp Верно ли, что любой язык из класса $\PP$ является полным относительно полиномиальной $m$-сводимости?

\prdag Докажите, что язык $\UNSAT$ является полным в классе $\coNP$ относительно полиномиальной $m$-сводимости.



\section{О сложности вычислений}

 Соотношение между классами $\PP$, $\NP$ и $\NPc$ $\coNP$ представляет собой центральный вопрос сложности вычислений.
Задача $\PP \stackrel{?}{\neq} \NP$ является основной в сложности вычислений и, по-видимому, безнадёжно трудной. Эта задача стала своего рода наследником теоремы Ферма, в том плане, что регулярно (хотя и не столь часто как в случае теоремы Ферма), находятся люди, которые «доказывают», что $\PP = \NP$ или обратное. Интерес к проблеме подогревается институтом Клэя, обещавшим за решение этой задачи $\$ 1\ 000\ 000$.  Тем не менее, недавно была предпринята первая серьёзная попытка действительно доказать, что $\PP \neq \NP$. Так что возможно мы всё же доживём до решения этого вопроса.


Сообщество верит, что $\PP \neq \NP$ и довольно многие результаты доказываются по модулю этой гипотезы. Более того, сложность этого вопроса используется на практике, в частности в криптографии. В этом курсе мы непосредственно с этим столкнёмся при изучении RSA-алгоритма шифрования. Тем не менее, то что задача лежит в $\NP$ и даже в $\NPc$ ещё вовсе не означает что её частный случай, \emph{экземпляр}  трудно решить. Это означает лишь, что задача трудна только для некоторых входов.


\section{Домашнее задание}

Задачи из канонического задания № 17.3, 23, задачи №1-4 из данного текста. 

Большинство задач, начиная с 21, я включу в следующее задание, последнее по теме «сложность вычислений». Оставшиеся задачи по этой теме из задавальника будут заданы при изучении чисел. При желании можно присылать решение задач из задавальника по этой теме не дожидаясь того, как я их задам.


\end{document}