Laboratory of Mathematical Logic at PDMI

Пятница, 15 апреля, комната 106. Начало в 17:30.

Докладчик: Ю. Лифшиц.

Тема: Вычислительная сложность обработки архивов.

Abstract

В докладе будет рассказано об универсальной модели архивов, основанной на контекстно-свободных грамматиках -- прямолинейных программах (straightline programs). Будет дан обзор сложностных результатов обработки архивов в этой модели. Кроме того, будет представлен результат докладчика об NP- и co-NP-трудности задачи ВЛОЖИМОСТИ архивов.