 \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{Домашнее задание}

Задачи из канонического задания на четвёртую неделю, задачи №2-4 из данного текста. 



\end{document}