\documentclass[11pt]{article}
\usepackage{fullpage}
\newcommand{\poly}{\textrm{poly}}
\newcommand{\pair}[1]{\langle #1\rangle}
\newcounter{задача}
\newcommand{\задача}{\refstepcounter{задача}%
\noindent\theзадача. }





\begin{document}

Задачи к экзамену.

\задача Постройте схему размера
$\poly(n)$, вычисляющую функцию
$f(x_1,\dots,x_n)$, которая принимает значение 1, если не менее
$n/2$ переменных среди
$x_1,\dots,x_n$ равны 1.


\задача Докажите
NP-полноту следующей проблемы.

Исходное данное: графы $G_1,G_2$.

Вопрос: есть ли у графа $G_2$ подграф, изоморфный
$G_1$ ?


\задача Докажите
NP-полноту следующей проблемы.

Исходное данное: конечная последовательность натуральных чисел
$x_1,\dots,x_n$.

Вопрос: найдется ли множество индексов $I\subset\{1,\dots,n\}$ такое,
что $\sum_{i\in I}x_i=\sum_{i\not\in I}x_i$ ?

\задача Докажите
NP-полноту следующей проблемы.

Исходное данное: Конечное семейство  конечных множеств и натуральное $k$.

Вопрос: Существует ли подсемейство, состоящее из $k$ попарно непересекающихся
множеств?


\задача Докажите
NP-полноту следующей проблемы.

Исходное данное: конечный граф $G$, подмножество $R$ множества его вершин
и натуральное $k$.

Вопрос: существует ли в $G$ поддерево из не более, чем  $k$ ребер,
включающее все вершины из $R$ (деревом называется связный граф без циклов,
поддеревом в $G$ называется любое дерево, все ребра которого принадлежат $G$)?

\задача Докажите, что для всех $i>0$ выполнено следующее:
$\Pi_i=\Sigma_i$  тогда и только тогда, когда
$\Sigma_{i+1}=\Sigma_i$.

\задача Докажите, что если $\Sigma_{i+1}=\Sigma_i$, то
$\Sigma_{n}=\Sigma_i$  для всех $n>i$.

\задача Граф называется жестким, если у него нет нетривиальных автоморфизмов
(то есть неединичных перестановок множества вершин, сохраняющих ребра).
Докажите, что множество пар $(G,k)$, для которых граф
$G$ имеет жесткий подграф из $k$ вершин, принадлежит $\Sigma_2$.

\задача Докажите, что если $A$ сводится по Тьюрингу за полиномиальное
время к $B\in\Sigma_i$, то
$A\in\Sigma_{i+1}$.

\задача Говорят, что язык $L$ принадлежит классу $Space(O(s(n)))$,
если найдется машина Тьюринга, распознающая
$L$ на зоне  $O(s(|x|))$.
Докажите, что $Space(O(n^2))\ne Space(O(n^3))$.
Докажите, что $Space(O(2^n))\ne PSPACE$.

\задача Докажите, что класс BPP замкнут относительно пересечений, объединений.

\задача 
Докажите, что если язык $B$ принадлежит BPP и
язык $A$ сводится по Тьюрингу за полиномиальное время к $B$,
то и $A$ принадлежит BPP.

\задача Докажите, что множество чисел вида $pq$, где $p,q$ простые числа,
принадлежит классу MA.

\задача Докажите, что множество всех пар чисел вида $\langle x,y\rangle$,
где $x$ взаимно простое с $y$ число, не являющееся
квадратом по модулю $y$,
принадлежит классу IP.

\задача Докажите, что класс MA включен в класс $\Sigma_2$

\задача Докажите, что класс AM включен в класс $\Pi_2$

\задача Докажите, что класс MA включен в класс AM

\end{document}