Упражнения

Покажите, что семейство схем глубины $O(\log n)$ также является семейством схем полиномиального размера.

Покажите, что 12 не является псевдопростым, поскольку оно не проходит некоторый тест Ферма.

Докажите, что если $A \leq_{\mathrm{L}} B$ и $B$ принадлежит NC, то $A$ принадлежит NC.

Покажите, что функцию чётности от $n$ входов можно вычислить ветвящейся программой с $O(n)$ узлами.

Покажите, что функцию большинства от $n$ входов можно вычислить ветвящейся программой с $O\left(n^{2}\right)$ узлами.

Покажите, что любую функцию от $n$ входов можно вычислить ветвящейся программой с $O\left(2^{n}\right)$ узлами.

ᴬ Покажите, что $\mathrm{BPP} \subseteq \mathrm{PSPACE}$.