Задачи

Пусть $A$ — регулярный язык над $\left\{ 0,1\right\}$. Покажите, что $A$ имеет сложность по размеру-глубине $(O(n), O(\log n))$.

• Булевой формулой называется булева схема, в которой у каждого вентиля только один выходной провод. Одна и та же входная переменная может встречаться в булевой формуле в нескольких местах. Докажите, что язык имеет семейство формул полиномиального размера тогда и только тогда, когда он принадлежит $\mathrm{NC}^{1}$. Не учитывайте соображения равномерности (uniformity).

• $\boldsymbol {k}$-головочным автоматом с магазинной памятью ($k$-МП-автоматом) называется детерминированный автомат с магазинной памятью с $k$ считывающими двунаправленными входными головками и стеком для чтения/записи. Определим класс $\mathrm{PDA}_{k}=\left\{ A \mid A\text{ распознаётся }k\text{-МП-автоматом}\right\}$. Покажите, что $\mathrm{P}=\bigcup_{k} \mathrm{PDA}_{k}$. (Подсказка: вспомните, что P равен чередующейся логарифмической памяти.)

Пусть $M$ — вероятностная машина Тьюринга, работающая за полиномиальное время, а $C$ — язык, для которого при некоторых фиксированных $0<\epsilon_{1}<\epsilon_{2}<1$

Покажите, что если $\mathrm{P}=\mathrm{NP}$, то $\mathrm{P}=\mathrm{PH}$.

Покажите, что если $\mathrm{PH}=$ PSPACE, то у полиномиальной иерархии лишь конечное число различных уровней.

Напомним, что $\mathrm{NP}^{S A T}$ — это класс языков, разрешаемых недетерминированными полиномиальными по времени машинами Тьюринга с оракулом для задачи выполнимости. Покажите, что $\mathrm{NP}^{\text{SAT }}=\Sigma_{2} \mathrm{P}$.

• Докажите малую теорему Ферма, приведённую в теореме 10.6. (Подсказка: рассмотрите последовательность $a^{1}, a^{2}, \ldots$. Что должно произойти, и почему?)

Докажите, что для любого целого $p>1$, если $p$ не является псевдопростым, то $p$ не проходит тест Ферма как минимум для половины всех чисел из $\mathcal{Z}_{p}^{+}$.

Докажите, что если $A$ — язык из L, то существует семейство ветвящихся программ $(B_{1}, B_{2}, \ldots )$, в котором каждая $B_{n}$ допускает в точности строки из $A$ длины $n$ и ограничена по размеру многочленом от $n$.

Докажите, что если $A$ — регулярный язык, то существует семейство ветвящихся программ $(B_{1}, B_{2}, \ldots )$, в котором каждая $B_{n}$ допускает в точности строки из $A$ длины $n$ и ограничена по размеру константой, умноженной на $n$.

Покажите, что если $\mathrm{NP} \subseteq \mathrm{BPP}$, то $\mathrm{NP}=\mathrm{RP}$.

Определим ZPP-машину как вероятностную машину Тьюринга, которой на каждой из её ветвей разрешены три типа выходных значений: допустить, отвергнуть и?. ZPP-машина $M$ разрешает язык $A$, если $M$ выдаёт правильный ответ на каждую входную строку $w$ (допустить, если $w \in A$, и отвергнуть, если $w \notin A$) с вероятностью не менее $\frac{2}{3}$, и $M$ никогда не выдаёт неправильный ответ. На любом входе $M$ может выдать? с вероятностью не более $\frac{1}{3}$. Кроме того, среднее время работы по всем ветвям $M$ на $w$ должно быть ограничено многочленом от длины $w$. Покажите, что $\mathrm{RP} \cap \operatorname {coRP}=\mathrm{ZPP}$, где ZPP — совокупность языков, распознаваемых ZPP-машинами.

Пусть $\operatorname {EQ}_{\mathrm{BP}}=\left\{ \left\langle B_{1}, B_{2}\right\rangle \mid B_{1} \text{ и } B_{2} \text{ — эквивалентные ветвящиеся программы}\right\}$. Покажите, что $\operatorname {EQ}_{\mathrm{BP}}$ coNP-полна.

Пусть BPL — совокупность языков, разрешаемых вероятностными машинами Тьюринга с логарифмической памятью и вероятностью ошибки $\frac{1}{3}$. Докажите, что $\mathrm{BPL} \subseteq \mathrm{P}$.

Пусть $C N F_{\mathrm{H}}=\left\{ \langle \phi \rangle \mid \phi \text{ — выполнимая кнф-формула, в которой каждый дизъюнкт содержит произвольное число литералов, но не более одного отрицательного литерала}\right\}$. В задаче 7.25 требовалось показать, что $C N F_{\mathrm{H}} \in \mathrm{P}$. Теперь приведите сведение в логарифмической памяти от CIRCUIT-VALUE к $C N F_{\mathrm{H}}$, чтобы заключить, что $C N F_{\mathrm{H}}$ является P-полной.