Колмогоровский семинар по сложности вычислений и сложности определений

Основанный акад. А.Н.Колмогоровым научный семинар посвящен изучению вопросов вычислительной сложности алгоритмических проблем, возникающих как собственно в теории алгоритмов, так и в математической логике, а также другим видам сложности — колмогоровской сложности (сложности описания конечных объектов), коммуникационной сложности и т.п.

Аннотация.
По предложению SIGACT, Андрей Ромащенко, Мариус Зиманд и я (Шень) пытаемся собрать некоторые давно открытые и мало изученные вопросы, относящиеся к колмогоровской сложности — их можно будет обсудить на занятии.

Аннотация.
Мы изучаем, как ранжировать кандидатов с помощью позиционных балльных правил. Каждая позиция в каждом индивидуальном ранжировании дает определенное количество очков, а общая сумма очков определяет итоговое ранжирование. Мы хотим, чтобы выполнялся принцип согласованности: когда какой-то кандидат удаляется, то итоговое ранжирование остальных кандидатов не меняется. Этот принцип важен в ситуациях, когда множество кандидатов может меняться, а итоговое ранжирование определяет последовательность действий: кого звать на интервью, если лучший претендент отказался? Кому вручать кубок, если победитель был пойман на допинге? Какой фильм рекомендовать к просмотру, если лучший фильм все уже смотрели? Изменится ли результат выборов при добавлении спойлера? К сожалению, полностью согласованных балльных правил не существует, однако, мы можем потребовать более слабую версию согласованности. Существуют балльные правила, которые остаются согласованными, если мы удаляем или добавляем единогласного победителя, например, атлета с подозрительно сильными результатами. Аналогично, мы можем удалять или добавлять единогласного проигравшего, например, спойлера на выборах. Почти ничего не ограничивающие по отдельности, вместе эти два принципа характеризуют однопараметрическое семейство с геометрическими, арифметическими и обратными геометрическими последовательностями очков. Наше семейство содержит три крайних правила: подсчет Борда, медальную систему и обратную медальную систему; мы приводим новые элегантные характеризации этих правил. Затем мы показываем как, эта постановка с одним параметром помогает выбирать подходящие балльные правила для различных приложений.