Ildarov932_6.tex.backup

\documentclass[a4paper,12pt]{article}

%%% Работа с русским языком
\usepackage{cmap}					          % поиск в PDF
\usepackage[T2A]{fontenc}			      % кодировка
\usepackage[utf8]{inputenc}               % кодировка исходного текста
\usepackage[english, russian]{babel}   % локализация и переносы


%%% Страница 
\usepackage{extsizes} % Возможность сделать 14-й шрифт
\usepackage{geometry}  
\geometry{left=20mm,right=20mm,top=25mm,bottom=30mm} % задание полей текста

\usepackage{titleps}      % колонтитулы
\newpagestyle{main}{
	\setheadrule{.4pt}                      
    \setfoot{А. Ш. Ильдаров | Б05-932}{}{\thepage} 
}      
\pagestyle{main}    % Устанавливает контитулы на странице


%%%  Текст
\setlength\parindent{0pt}         % Устанавливает длину красной строки 0pt
\sloppy                                        % строго соблюдать границы текста
\linespread{1.3}                           % коэффициент межстрочного интервала
\setlength{\parskip}{0.5em}                % вертик. интервал между абзацами
%\setcounter{secnumdepth}{0}                % отключение нумерации разделов
%\setcounter{section}{-1}         % Чтобы сделать нумерацию лекций с нуля
\usepackage{multicol}				          % Для текста в нескольких колонках
%\usepackage{soul}
\usepackage{soulutf8} % Модификаторы начертания

\usepackage{listings} % Code listings


%%% Гиппер ссылки
\usepackage{hyperref}
\usepackage[usenames,dvipsnames,svgnames,table,rgb]{xcolor}
\hypersetup{				% Гиперссылки
	unicode=true,           % русские буквы в раздела PDF\\
	pdfstartview=FitH,
	pdftitle={Заголовок},   % Заголовок
	pdfauthor={Автор},      % Автор
	pdfsubject={Тема},      % Тема
	pdfcreator={Создатель}, % Создатель
	pdfproducer={Производитель}, % Производитель
	pdfkeywords={keyword1} {key2} {key3}, % Ключевые слова
	colorlinks=true,       	% false: ссылки в рамках; true: цветные ссылки
	linkcolor=blue,          % внутренние ссылки
	citecolor=green,        % на библиографию
	filecolor=magenta,      % на файлы
	urlcolor=NavyBlue,           % на URL
}


%%% Для формул
\usepackage{amsmath}          
\usepackage{amssymb}


%%%%%% theorems
\usepackage{amsthm}  % for theoremstyle

\theoremstyle{plain} % Это стиль по умолчанию, его можно не переопределять.
\newtheorem{theorem}{Теорема}[section]
\newtheorem{prop}[theorem]{Утверждение}
\newtheorem{lemma}{Лемма}[section]
\newtheorem{sug}{Предложение}[section]

\theoremstyle{definition} % "Определение"
\newtheorem{Def}{Определение}
\newtheorem{corollary}{Следствие}[theorem]
\newtheorem{problem}{Задача}[section]

\theoremstyle{remark} % "Примечание"
\newtheorem*{nonum}{Решение}
\newtheorem*{defenition}{Def}
\newtheorem*{example}{Пример}
\newtheorem*{note}{Замечание}


%%% Работа с картинками
\usepackage{graphicx}                           % Для вставки рисунков
\graphicspath{{images/}{images2/}}        % папки с картинками
\setlength\fboxsep{3pt}                    % Отступ рамки \fbox{} от рисунка
\setlength\fboxrule{1pt}                    % Толщина линий рамки \fbox{}
\usepackage{wrapfig}                     % Обтекание рисунков текстом
\graphicspath{{images/}}                     % Путь к папке с картинками

\newcommand{\drawsome}[1]{            % Для быстрой вставки картинок
    \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.7]{#1}
            \label{fig:first}
    \end{figure}
}
\newcommand{\drawsomemedium}[1]{
    \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.45]{#1}
            \label{fig:first}
    \end{figure}
}
\newcommand{\drawsomesmall}[1]{
    \begin{figure}[h!]
            \centering
            \includegraphics[scale=0.3]{#1}
            \label{fig:first}
    \end{figure}
}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}

\lstset{style=mystyle}

%%% облегчение математических обозначений
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
%\newcommand{\C}{\mathbb{C}}             % команда уже определена где-то)
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\brackets}[1]{\left({#1}\right)}      % автоматический размер скобочек
% Здесь можно добавить ваши индивидуальные сокращения  

\renewcommand{\labelenumii}{\theenumii}
\renewcommand{\theenumii}{\theenumi.\arabic{enumii}.}

\begin{document}
\section*{Домашнее задание № 6. Сложность вычислений.}%
\label{sec:Домашнее задание № 6. Сложность вычислений.}

\subsection*{Задача 1.}%
\label{sub:Задача 1.}
\paragraph{Без требования конечности $\boldsymbol{Q}$.}
Для всех возможных входных данных, например закодированных в двоичном виде, заведем свое состояние, 
а для каждого из состояний определим переход в $q_a$ или  $q_r$. 
По мере считывания ввода будем переходить из состояния, соответсвующего префиксу,
в состояние соответсвующее следующему 
префиксу и так пока не прочитаем целиком.

\paragraph{Без требования конечности $\boldsymbol{\Sigma}$.}
Будем считать входные данные одним символом, для которого определим переход в состояние $q_a$ или $q_r$.

\paragraph{Без требования конечности $\boldsymbol{\Gamma}$.}
Для всех возможных входных данных, например закодированных в двоичном виде, заведем свой сивол в ленточном алфавите,
а для каждого из символов определим переход в $q_a$ или $q_r$.
По мере считывания ввода будем записывать актуальный на данный момент символ в отдельную ячейку, 
а завершив ввод, совершим необходимый переход.

\subsection*{Задача 2.}%
\label{sub:Задача 2.}
Покажем, что $\text{ CLIQUE } \leq_p \text{ SUBGRAPH-ISO }$. \\
Определим полиномиально-вычислимую функцию $f: (G, k) \mapsto (G, K_k)$, тогда
\[
    \forall G, k \hookrightarrow  (G, k) \in \text{ CLIQUE } \iff f((G, k)) \in \text{ SUBGRAPH-ISO }
.\] 
Значит SUBGRAPH-ISO --- NP-полный в силу NP-полноты CLIQUE.

\newpage

\subsection*{Задача 3.}%
Покажем, что $\text{ 3SAT } \leq_p \text{ INDPNDC } = \{G: \alpha(G) = \frac{1}{3}\lvert V(G) \rvert\}$. \\
Определим полиномиально-вычислимую функцию $f$, которая формуле ставит в соответствие граф, 
построенный следующим образом: 

\begin{itemize}
    \item Для каждого конъюнкта построим треугольник, каждая из вершин которого соответствуют переменной.
    \item Вне треугольников соединим вершины ребрами, если они соответствуют одной переменной и ее отрицанию. 
\end{itemize}

Покажем теперь что \underline{$\varphi \in \text{ 3SAT } \implies f(\varphi) \in \text{ INDPNDC}$}: \\
Имея набор переменных, на котором $\varphi$ возвращает $1$, в каждом из конъюнктов можем выбрать по одному истинному дизъюнкту. 
Именно они и образуют независимое множество, ведь они не будут связаны ребрами вне треугольника,
так как связанные ребрами вершины не могут соответствовать одновременно истинным элементам по построению. 
В каждом треугльнике будет выбрана ровно 1 вершина, а значит $\alpha(G) = \frac{1}{3}\lvert V(G) \rvert$ 

\underline{В другую сторону:} \\
Если мы имеем $\alpha(G) = \frac{1}{3}\lvert V(G) \rvert = k$, то по построению и вышеизложенному доводу,
каждая из вершин независимого множества соответствует дизъюнктам из разных конъюнктов, а потому мы можем установить эти дизъюнкты истинными.
Так как вершинами соединены взаимоисключающие дизъюнкты, формула станет истинной. 

\subsection*{Задача 5.}%
\label{sub:Задача 5.}
Покажем, что $\text{ DHAMPATH } \leq_p \text{ UHAMPARTITION } $. \\
Определим полиномиально-вычислимую функцию $f: G \mapsto (G, 1)$, тогда просто по определию UHAMPARTITION,

\[
    \forall G \hookrightarrow  G \in \text{ DHAMPATH } \iff f(G) \in \text{ UHAMPARTITION }
.\] 

\newpage

\subsection*{Задача 6.}%
\label{sub:Задача 6.}


\subsection*{Задача 7.}%
\label{sub:Задача 7.}
Когда будет доказано, что P = NP, SAT будет разрешим за полиномиальное время. Тогда, имея выполнимую формулу $\varphi$, 
найдем выполняющий набор $(x_1, x_2, ..., x_n)$ следующим образом: \\
Подставим $x_1 = 0$ в $\varphi$ и рассмотрим получившуюся формулу  $\varphi_1$. \\
Если она выполнима, то запомним  $x_1 = 0$, в противном случае она будет выполнима при  $x_1 = 1$, ведь  $\varphi$ выполнима, 
тогда запомним $x_1 = 1$. Повторим процедуру для всех переменных. Всего шагов $n$, каждый из них имеет полиномиальное время, 
а значит определение выполняющего набора так же займет полиномиальное время. Если выполняющего набора нет, то $\varphi$ невыполнима, 
а это мы также можем установить за полиномиальное время.


\subsection*{Задача 8.}%
\label{sub:Задача 8.}
1. L лежит в P, ведь можем построить верификатор, который, принимая длину входного слова $k$ в качестве сертификата, установит, 
есть ли в языке слово длиной $k$ и перейдет в соответсвующее состояние. 

2. P $\subset$ NP $\implies$ L $\in$ NP, а тогда имеем  L~--- NP-complete. 

3. Теперь, раз L~--- NP-complete, можем утверждать, что  $\exists f \text{ --- полиномиально-вычислимая}: \forall x \hookrightarrow x \in \text{ SAT } \iff  f(x) \in L$.

4. Теперь, имея эту моднейшую функцию, покажем как разрешить $SAT$ за полиномиальное время: \\
Заведем массив, назовем его $Adam$, изначально заполненный нулями. Будем говорить что  $Adam[i] = True \iff 1^i \notin L.$ \\
Тогда проверка $\varphi$ на выполнимость сводится к:
\begin{enumerate}
    \item Если у $\varphi$ нет переменных, то она выполнима если она истинна. Иначе запомним  $Adam[f(\phi)] = True$ и скажем что она невыполнима.
    \newpage
    \item В противном случае: \\
        Возьмем какую-то переменную в $\varphi$.
         \begin{itemize}
            \item Установим эту переменную истинной, а дальше проверим, что о получившейся формуле $\varphi_1$ говорит $Adam$. \\
                Если еще не было выяснено, что $\varphi_1$ невыполнима, то рекурсивно проверим $\varphi_1$ и вернем результат. 
            \item Установим эту переменную ложной, получив формулу $\varphi_0$, а дальше снова обратимся к $Adam$. \\
                Если еще не было выяснено, что $\varphi_0$ невыполнима, то рекурсивно проверим $\varphi_0$ и вернем результат. 
            \item Если обе подформулы были помечены $Adam$ как невыполнимые, то и всю формулу пометим невыполнимой, вернем этот результат.
        \end{itemize}
\end{enumerate}

На каждом шаге рекурсии мы уменьшаем рассматриваемую длину формулы на $1$, а значит всего шагов будет  $poly(n)$.
При этом проверка на каждом шаге так же занимает $poly(n)$, значит и вся процедура работает за $poly(n)$.
Значит мы доказали, что SAT разрешим за полиномиальное время, то есть P = NP.


\subsection*{Задача 9.}%
\label{sub:Задача 9.}
Заметим, что критерием принадлежности к $L^*$ является $w = \varepsilon \vee w \in L \vee w = uv, u \in L^*, v \in L^*.$ \\
Пусть у нас имеется $w = w_1 \ldots w_k$. \\
Построим таблицу, назовем ее $Adam$, изначально заполненную нулями. Будем говорить, что  $Adam[i][j] = True$ если  $w_i \ldots w_j \in L^*$. \\
Будем итерироваться по всем подстрокам фиксированной длины, начиная с 1. \\
Пусть очередная подстрока это $w_i \ldots w_j$. \\
Применим процедуру к этой подстроке:
\begin{itemize}
    \item Если процедура дала положительный результат, то установим $Adam[i][j] = True$. 
    \item В противном случае, если $\forall k \in (i, j - 1) \hookrightarrow Adam[i][k] = True \land Adam[k][j] = True$, то есть про все разбиения подстроки известно, что они лежать в языке,
        то можем сдеать вывод что и подстрока лежит в языке, то есть $Adam[i][j] = True.$
\end{itemize}

Тогда для определения принадлежности слова достаточно проверить что  $Adam[1][n] == True.$
При каждом рекурсивном вызове длина рассматриваемого слова уменьшается, при этом каждый вызов работает за $poly(n)$, значит  $P:*$ разрешим за  $poly(n)$, то есть лежит в классе  $P$.

\subsection*{Задача 10.}%
\label{sub:Задача 10.}
Пусть $L_1, L_2 \in \text{ NP }$, разрешаются машинами $M_1, M_2$.
\paragraph{Пересечение.}%
\label{par:Пересечение.}
    Получив вход, запустим $M_1$, если  получили  $q_r$, то перейдем в  $q_r$. \\
    В противном случае, запустим  $M_2$, если получили  $q_r$, то вернем  $q_r$. \\
    Иначе же перейдем в $q_a$.

\paragraph{Объединение.}%
\label{par:Объединение.}
    Получив вход, запустим $M_1$, если  получили  $q_a$, то перейдем в $q_a$  \\
    В противном случае, запустим  $M_2$, если получили  $q_a$, то перейдем в $q_a$. \\
    Иначе же перейдем в $q_r$.

\paragraph{Звезда Клини.}%
\label{par:Звезда Клини.}
    Если получили $\varepsilon$, то перейдем в  $q_a$. \\
    В противном случае недетерменированым образом разобъем входное слово на подслова. В случае если для хотябы одного слова машина исходного языка перешла в  $q_r$, то перейдем в  $q_r$,
    иначе же перейдем в  $q_a$.



Каждый раз мы сводили решение к применению исходной машины $poly(n)$ число раз, предварительно сделав не более  $poly(n)$ шагов, каждый из языков принадлежит классу NP.

\end{document}