= <NAME> ДЗ №4

#set par(
  justify: true,
)


= Задача 1
Какие из включений $subset.eq, supset.eq$ имеют место между классами TIME($n^2$) и SPACE($n^2 log n$)?

== Решение
Для МТ имеем теорему о соотношении между T и S: $S_M (arrow(x)) lt.eq.slant T_M (arrow(x))$.

TIME($n^2$) $arrow.r.double$  $T_M (arrow(x)) = O(n^2)$, где $n=$  $bar.v$$arrow(x)$$bar.v$. Значит для МТ этого класса зона будет  $lt.eq.slant O(n^2)$.

SPACE($n^2 log n$) $arrow.r.double$  $S_M (arrow(x)) = O(n^2 log n)$, значит время МТ этого класса будет $gt.eq.slant O(n^2 log n)$.

Из последовательного сравнения машин видим, что у машин класса TIME($n^2$) и время, и зона меньше таковых у маишн класса SPACE($n^2 log n$), значит TIME($n^2$) $subset.eq$ SPACE($n^2 log n$).

= Задача 2
Пусть язык $L$ распознается 0−1-машиной $M$, такой что $S_M (n) lt.eq.slant f(n)$ при всех $n in N$. Докажите,
что для каждого $epsilon > 0$ существует 0−1-машина $M'$, распознающая язык $L$, такая что $S_(M') lt.eq.slant n + epsilon f(n)$.


== Доказательство
$square$ 

Идея - сопоставить последовательности k входных символов исходной машины комбинацию этих символов записанную в одну ячейку, где $k = ceil.l 1/epsilon ceil.r$.

$bracket.l 1 bracket.r bracket.l 0 bracket.r bracket.l 1 bracket.r...$ $arrow.r$ $bracket.l 101 bracket.r ...$

Для этого потребуется перекодирование исходного входного алфавита машины $M$ и дальнейшая эмуляция $M$ машиной $M'$ на преобразованном новом алфавите. 

Для эмуляции сопоставим состояния старой машины с состояниями новой, это требует храния в состояниях новой $M'$ некоторый субъячеечный индекс отвечающих состоянию исходной машины на исходных раздельных символах, то есть состоянию машины $M$ $q_k$ будет соответствовать состояние $q'_(i k j)$ машины $M'$, где i -- номер новой ячейки, k -- соответсвие состояцию исходной машины, а j -- позиция символа в новой ячейке для изменения.

Время алгоритма нам не важно исходя из условия задачи. Зато благодаря преобразованию зона эмулирующей машины будет $f(n) / k lt.eq.slant epsilon f(n)$ (так как k окргляли вверх). При этом сам вход изначально занимал n. 

Таким образом для всей конструкции имеем $S_M' lt.eq.slant n + f(n)/k lt.eq.slant n + epsilon f(n)$.

#align(right, $square.filled$)