= <NAME> ДЗ №3

#set par(
  justify: true,
)


= Задача 1
Докажите, что из L, M $in$ P следуют #overline[L], L $sect$ M, L $union$ M $in$ P  (здесь #overline[L] $ = Sigma^* without$ L), а также L · M $in$ P, где L · M = {uv | u $in$ L, v $in$ M} есть множество всевозможных конкатенаций двух слов из L и M соответственно.

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

=== 1. #overline[L] $in$ P
$square$ Если $L in P$, значит существует 0-1 poly м.т. $K$: $cases(
  K(arrow(x)) = 1 \, arrow(x) in L,
  K(arrow(x)) = 0 \, arrow(x) in.not L
)$

Значит, так же можно построить такую poly м.т. $K'$, которая будет выдавать противополоные $K$ результаты (можно взять машину $K$ и добавить к ней операцию инвертирования ответа, сложность которой $O(1)$, значит сама машина останется poly).

Тогда имеем $K'$: $cases(
  K'(arrow(x)) = 0 \, arrow(x) in L arrow.l.r.double.long arrow(x) in.not overline(L),
  K'(arrow(x)) = 1 \, arrow(x) in.not L arrow.l.r.double.long arrow(x) in overline(L)
)$ $arrow.r.double$ $cases(
  K'(arrow(x)) = 1 \, arrow(x) in overline(L),
  K'(arrow(x)) = 0 \, arrow(x) in.not overline(L)
)$

Таким образом имеем полиномиальную м.т. $K'$, распознающую язык $overline(L)$, значит $overline(L) in P$.

#align(right, $square.filled$)

=== 2. L $sect$ M $in$ P
$square$ Если $L, M in P$, значит существует 0-1 poly м.т. $K$: $cases(
  K(arrow(x)) = 1 \, arrow(x) in L,
  K(arrow(x)) = 0 \, arrow(x) in.not L
)$ 
и $Y$: $cases(
  Y(arrow(x)) = 1 \, arrow(x) in M,
  Y(arrow(x)) = 0 \, arrow(x) in.not M
)$

Соответственно, если слово $arrow(y) in L sect M$, то оно может быть распознано любой из приведенных машин, работающих за полиномиальное время, то есть существует poly м.т. (например $K$), распознающая все слова из $L sect M$ за полином $arrow.r.double$ $L sect M in P$.


#align(right, $square.filled$)


=== 3. L $union$ M $in$ P
$square$ Если $L, M in P$, значит существует 0-1 poly м.т. $K$: $cases(
  K(arrow(x)) = 1 \, arrow(x) in L,
  K(arrow(x)) = 0 \, arrow(x) in.not L
)$ 
и $Y$: $cases(
  Y(arrow(x)) = 1 \, arrow(x) in M,
  Y(arrow(x)) = 0 \, arrow(x) in.not M
)$

Соответственно, для распознания слова $arrow(y) in L union M$, можно сконструировать машину $Z$, которая будем представлять собой последовательно соединенные машины $K$ и $Y$ через логическое сложение: сначала отрабатывает программа машины $K$, записывает результат в выходную ленту, если результат 1, то завершаемся, если 0, то затем отрабатывает программа машины $Y$, и прибавляет свой результат к уже записанному результату алгоритма $K$, обе машины работают за полином, операция прибавления однобитовых чисел в данном случае $O(1)$, так как есть всего два варианта 0 + 0 и 0 + 1, для обоих нужно одно элементарное действие, получаем, что итоговая сложность составной машины $Z$ тоже полином.

Таким образом, построили 0-1 poly м.т. $Z$: $cases(
  Z(arrow(x)) = 1 \, arrow(x) in L union M,
  Z(arrow(x)) = 0 \, arrow(x) in.not L union M
)$ 
$arrow.r.double$ $L union M in P$


#align(right, $square.filled$)


=== 4. L · M $in$ P, где L · M = {uv | u $in$ L, v $in$ M}
$square$ Если $L, M in P$, значит существует 0-1 poly м.т. $K$: $cases(
  K(arrow(x)) = 1 \, arrow(x) in L,
  K(arrow(x)) = 0 \, arrow(x) in.not L
)$ 
и $Y$: $cases(
  Y(arrow(x)) = 1 \, arrow(x) in M,
  Y(arrow(x)) = 0 \, arrow(x) in.not M
)$

Для распознавания конкатенации слов из  $L$ и $M$ можно воспользоваться следующим алгоритмом: мы знаем, что первая часть слова у нас из $L$, но не знаем какой длины, тогда мы можем сделать следующее - идти по слову и на каждом шаге запускать алгоритм машины $Y$, распознающий слово из $M$, если не распозналось, то сдвигаем головку вперед и повторяем, если слово распозналось, значит мы нашли "стык" двух слов, далее можно заменить уже распознанную часть слова на $\#$ и запустить алгоритм машины $K$, по результату распознавания последнего уже можно судить о нахождении слова в $L dot M$. Условие выхода при неудачном распозновании следующее, если в ходе прохода алгоритмом $Y$ по слову мы дошли до конца, так ничего и не распознав, значит нет суффикса слова $in M$, значит слово точно $in.not L dot M$. 

В описанном алгоритме мы в худшем случае запускаем poly алгоритм машины $Y$ n раз, где n -- длина входа, таким образом увеличиваем стпень полинома на 1, но он все еще полином, далее, в случае упеха алгоритма $Y$, отработает еще poly аглоритм $K$, итого в конечном счете имеем все еще полином.

Таком образом, мы описали 0-1 м.т. распознающую слова из  $L dot M$ за полиномиальное время, значит  $L dot M in P$.


#align(right, $square.filled$)



= Задача 2
Докажите, что задача распознавания наличия треугольника (т. е. подграфа, изоморфного $K_3$) в
графе лежит в P. Граф задан матрицей смежности.

== Доказательство
$square$
Обозначим матрицу смежности за $A$. Тогда чтобы понять есть ли треугольник (цикл длины 3) в графе, достаточно посмотреть на след матрицы $A^3$. Перемножение матриц занимает полиномиальное время (например, наивный алгоритм - $O(n^3)$), умножение нужно выполнить 2 раза, подсчет следа итоговой матрицы - $O(n)$, итого получаем, что общая сложность алгоритма проверки наличия треугольника - $O(n^3)$.

По тезису Чёрча-Тьюринга описанный выше алгоритм может быть выполнен на м.т. не более чем с полиномиальным замедлением относительно сложности программы $O(n^3)$ в РЯП. Полином от $n^3$ тоже полином $arrow.r.double$ значит существует работающая за полином м.т. $M$, распознающая наличие треугольника в графе $arrow.r.double$ задача $in P$.

#align(right, $square.filled$)





