Вторник 23.09. А.В. Смаль (ПОМИ): "Каталитические вычисления и регистровые программы за пределами логарифмической глубины"
PDMI seminars
Тема: Каталитические вычисления и регистровые программы за пределами логарифмической глубины
Место: zoom
Время: 23.09.2025, 15: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.org%2F10.4230%2FLIPIcs.MFCS.2025.6&data=05%7C02%7Cmasnnv%40bath.ac.uk%7C4e63254ed16c40e7ad6208ddf52b98b4%7C377e3d224ea1422db0ad8fcc89406b9e%7C0%7C0%7C638936289808820632%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=45AP4PmotN6yLZpO04I5dKgvs4ilgOeAHd%2FR%2B%2FNBEM8%3D&reserved=0