Mathematical Logic and Discrete Mathematics at PDMI

Вторник, 23 сентября, zoom. Начало в 16:00.

Докладчик: А.В. Смаль (ПОМИ).

Тема: Каталитические вычисления и регистровые программы за пределами логарифмической глубины.

Abstract

В работе Buhrman, Cleve, Koucký, Loff, и Speelman (STOC 2014) авторы
определили сложностной класс CSPACE(s,c) – класс задач, разрешимых в
на машине Тьюринга с обычной рабочей лентой размера s и с
дополнительной "каталитической" лентой размера c, чьё начальное
содержимое должно быть восстановлено в конце вычисления. Они показали,
что равномерные схемы TC1 вычислимы в каталитическом логарифмическом
пространстве, то есть CL=CSPACE(O(log n), 2^{O(log n))}), тем самым
предоставив веские доказательства того, что наличие доступа к
каталитической ленте даёт дополнительную вычислительную мощность. Их
исследование сосредоточено на арифметической модели, называемой
регистровыми программами, которая с тех пор стала одним из центральных
объектов изучения.

Понимание CL остаётся важной открытой проблемой, поскольку "TC1 лежит
в CL" остаётся наиболее мощным включением такого типа на сегодняшний
день. В докладе будет рассказано о том, как используя регистровые
программы показать, что класс SAC2 булевых схем полиномиального
размера и глубины O(log n), с ограниченным арностью гейтов "И" и
неограниченной арностью гейтов "ИЛИ", можно вычислить на
каталической машине Тьюринга с рабочей лентой размера o(log n)
и каталитической лентой почти полиномиального размера.

По совместной работе https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or...