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

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

Date:

Friday, March 17, 2017 - 17:15

Abstract:

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