Пятница 17.03. Александр Рыбалов: "Генерический подход к алгоритмическим проблемам"

Докладчик: 
Александр Рыбалов
Дата: 
Friday, March 17, 2017 - 17:15
Место: 
ауд. 203
Аннотация: 

Генерический подход к вычислимости и вычислительной сложности был предложен И.Каповичем, А.Мясниковым, В.Шпильрайном и П.Шуппом в 2003 г. В рамках этого подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве "почти всех" входов. Такие входы образуют так называемое генерическое множество. Понятие "почти все" формализуется введением естественной меры на множестве входных данных. Данный подход схож с изучением сложности в среднем, но, в отличие от него, "плохие входы" игнорируются - алгоритм на них выдает ответ "не знаю". Это позволяет, также изучать генерическую сложность неразрешимых проблем. В докладе будет дан обзор результатов по генерической сложности различных классических проблем.