
 \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$ и $\coNP$ II}
\end{center}

\bigskip

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

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

\end{enumerate}

	


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

На семинаре мы разобрались почему задача о поиске гамильтонового пути в ориентированном графе является $\NP$-полной задачей. Осталось разобраться со следующими задачами:

\prp Доказаать, что язык $\rm{UHAMPATH}$ каждое слово которого состоит из описания неориентированного графа и двух вершин $s,t$, таких что из $s$ в $t$ есть гамильтонов путь, является $\NP$-полным языком.\\
\smallskip
\textbf{Указание:} построить сводимость языка $\rm{HAMPATH}$ к языку $\rm{UHAMPATH}$ путём замены каждой вершины $u$ на три вершины $u_{in},u_{med},u_{out}$, соединённые последовательно рёбрами, причём, все рёбра ведущие в $u$ направляются в $u_{in}$, а все рёбра исходящие из $u$ направляются в $u_{out}$.

\prp Свести задачу о поиске гамильтонова цикла к задаче о поиске гамильтонова пути. Брать ориентированный или неориентированный граф -- на ваш выбор.
\bigskip

В конце семинара мы обсуждали сводимость по Тьюрингу, которая устроена следующим образом. Будем говорить, что язык $L$ сводится к языку $L^\prime$ по Тьюрингу за полиномиальное время и обозначать это как $L \leq^p_T L^\prime$, если есть машина Тьюринга $M_{L^\prime}$ с оракулом $L^\prime$, которая распознаёт $L$. То есть машина $M_{L^\prime}$ может проверять принадлежность любого слово языку $L^\prime$. Я обнаружил, что дал задачу в неправильной формулировке. Решение задачи в правильной формулировке было практически полностью получено на семинаре.

\prp Рассмотрим класс языков $\C$, сводимых к языку $\SAT$ в следующем смысле: для каждого языка $L$ из $\C$ существует полиномиальная машина Тьюринга $M_{\SAT}$, которая распознаёт язык $L$, причём машина $M_{\SAT}$ делает не более одного запроса к оракулу. Доказать, что класс $\C = \NP\cup\coNP$.

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

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


\end{document}