Laboratory of Mathematical Logic at PDMI

Пятница, 21 декабря, комната 106. Начало в 17:45.

Докладчик: А. Кожевников.

Тема: Сложность в среднем задачи равенства слов для полугруппы Цейтина.

Abstract

В докладе будет рассказано о двух модификациях полугруппы Цейтина Ц, позволяющих доказать DistNP-полноту задачи равенства случайных слов в Ц. Первая модификация заключается в изменении представления кода символов полугруппы G, которую моделирует Ц. Вторая позволяет работать с произвольными полугруппами, а не только с полученными из групп. Доклад основан на совместной работе с И.Монаховым и С.Наумовым.