
 \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 Задача $\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 Задание 10}

\medskip

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

\bigskip

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

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

\end{enumerate}

\section{Машины Тьюринга и формальные языки}

	Под формальным языком $L$ мы понимаем некоторое подмножество множества всех слов над алфавитом $\Sigma$. В этой теме слова «язык» и «задача» являются синонимами, поскольку речь идёт только о задачах распознавания, то есть задач проверки принадлежности слова языку. То есть задача перемножить два числа не является задачей в наших терминах в рамках этого раздела.
	
	Каждому языку мы ставим в соответствие машину Тьюринга, которая его распознаёт. 

\begin{Def} 

	\emph{Детерминированная Машина Тьюринга} $M$  имеет $l$ лент, $k$ головок, множество состояний $Q$, множество принимающих состояний $Acc \subset Q$,  входной алфавит $\Sigma$, функцию перехода $\delta : \Sigma^k\times Q \to \{0,+1,-1\}^k\times \Sigma^k\times Q  $ -- за такт работы машина меняет состояние, символы под каждой головкой и двигает каждую головку влево, вправо или оставляет её неподвижной. На машину могут быть наложены ограничения, например, полиномиальное время работы или полиномиальная память по входу. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово $x$. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово. 
		
\end{Def}


Будем говорить, что машина Тьюринга $M$ вычисляет функцию $M(x)$, которая равна $1$, в случае если машина $M$ на входе $x$ останавливается в принимающем состоянии, если машина $M$ на входе $x$ останавливается в не принимающем состоянии, то $M(x) = 0$, а если машина $M$ не останавливается на входе $x$, то функция $M(x)$ не определена.

$$
	M(x) = 
	\begin{cases}
		1, & M \text{ остановилась в принимающем состоянии на $x$;} \\
		0, & M \text{ остановилась в не принимающем состоянии на $x$;}\\ 
		\uparrow, & M \text{ не остановилась, функция не определена на $x$.}
	\end{cases}
$$


	 Машина $M$ \emph{принимает} язык $L$, если она принимает каждое слово из языка $L$, если машина $M$ принимает язык $L$ и к тому же все слова, принимаемые машиной $M$, лежат в языке $L$,  то будем говорить, что машина $M$ \emph{распознаёт} $L$. Язык, распознаваемый машиной $M$ будем обозначать $L(M)$.


\begin{Remark}
	Определение языка, распознаваемого машиной Тьюринга, при беглом взгляде кажется естественным, но на самом деле оно весьма коварно. На слова не из $L$ ограничений не накладывается, поэтому на них машина $M$ может и не останавливаться вовсе.
\end{Remark}

Языки, распознаваемые машинами Тьюринга, называются \emph{(рекурсивно-)перечислимыми} языками или \emph{распознаваемыми} языками.

Будем говорить, что машина Тьюринга $M$ разрешает язык $L$, если она останавливается на всех входах и распознаёт язык $L$.

Языки разрешимые машинами Тьюринга образуют класс \emph{рекурсивных} языков, также называемыми \emph{разрешимыми}.
 

Аналогично определяется и недетерминированная машина Тьюринга.
Если не оговорено противного, мы будем считать, что машина Тьюринга $M$ имеет одну ленту и одну головку.

\bigskip

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

\bigskip


Поскольку машины Тьюринга имеют конечное описание, то их описание можно закодировать. Будем обозначать $M_\alpha$ машину Тьюринга, описание которой закодирована строкой $\alpha$. Мы можем просто занумеровать все возможные описания машин Тьюринга и считать, что $\alpha$ -- натуральное число. Если же это неудобно, мы можем считать, что $\alpha$ есть просто строка, содержащая описание машины Тьюринга, и если описание некорректно, то будем считать, что $M_\alpha$ -- машина Тьюринга, распознающая пустой язык.


Из возможности кодирования описаний машин Тьюринга следует, что существует машина Тьюринга, которая получает на вход описание $\alpha$ и вход $x$ и проделывает работу машины $M_\alpha$ на входе $x$. Такую машину Тьюринга будем называть \emph{универсальной} и обозначать $UM$.


\section{Разрешимые и неразрешимые задачи}

Прежде чем говорить о сложности задачи надо доказать, что она разрешима. Это далеко не всегда так даже в очень естественных случаях.

\begin{Example} Пусть язык $L$ лежит в классе $\CFL$. Проверка условия $L \stackrel{?}{=} \Sigma^*$  -- неразрешимая задача.
\end{Example}
	
Одна из самых распространённых неразрешимых задач -- проблема останова. Под проблемой останова понимается язык $\HALT$ состоящий из описаний всех машин Тьюринга, останавливающихся на пустом входе.

\begin{Example}
	$$\HALT = \{ \alpha\, |\, M_\alpha(\eps) = 1 \} $$
\end{Example}

\upr Докажите что язык $ \HALT $ является неразрешимый. Если доказать самостоятельно не получается, обратитесь к литературе.

\bigskip

Язык $L$ называется \emph{перечислимым}, если существует такая МТ $M$, которая выводит все слова из языка. МТ $M$ может вообще говоря никогда не остановится, но если слово $w$ лежит в $L$, то машина $M$  должна вывести $w$ через некоторое, быть может очень большое, число тактов.

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

\upr Докажите, что язык $\HALT$ является перечислимым.

\upr Докажите, что язык $L$ является разрешимым тогда и только тогда, когда языки $L$ и $\bar L$ перечислимы.


\section{Классы $\PP$ и $\NP$}

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

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

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


Класс $\PP$ состоит из объединения всех языков, лежащих в $\DTIME(O(n^c))$, то есть

$$
 \PP = \bigcup_{c \geq 0} \DTIME(O(n^c))
$$

Аналогично определим класс $\NP$:

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

\prdag Покажите, что в определении класса $\PP$ неважно сколько лент и головок у машины Тьюринга $M$. То есть, если язык $L$ распознаётся за полиномиальное время машиной Тьюринга $M$ с $k$ лентами и $l$ головками, то он распознаётся и некоторой машиной $M^\prime$ с одной лентой и одной головкой.

\bigskip

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

\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$ мы будем называть сертификатом для слова $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 \subset \Sigma_1^*$ существует такая вычислимая функция $f : \Sigma_1^* \to \Sigma_2^*$, что слово $x$ принадлежит $A$ тогда и только тогда, когда слово $f(x)$ принадлежит языку $B$. Будем говорить, что язык $A$ сводится к языку $B$ $m$-сводимостью и обозначать это как $A \leq_m B $.
\end{Def}



\begin{Def}
	Пусть для языка $A \subset \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$, то задача $A$ является неразрешимой.

\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$ и $\NPc$ нас также будет интересовать класс $\coNP$, состоящий из языков, являющихся дополнением к языкам из $\NP$. То есть, если язык $L$ лежит в классе $\NP$, то язык $\bar L$ лежит в классе $\coNP$ 



\begin{comment}
	


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

Задача $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$-полной задачи.

\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$.

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


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

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

\end{comment}

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

Задачи из канонического задания № 8, 11-15, задача 2 из данного текста.


\end{document}