DM Seminar

Discrete Mathematics Seminar

Семинар 14 декабря 1999 года

Вторник, 14 декабря, комната 106. Начало в 18:00.

14 декабря.
Э.Гирш "Сложность по Колмогорову: неожиданные примеры применения"
С помощью сложности по Колмогорову и _элементарной_ теории чисел будут заново (более просто) доказаны следующие результаты:
-- Valiant-Vazirani lemma о сведении SAT к SAT для одновыполнимых формул; -- Sipser's lemma; -- BPP \subset \Sigma_2^p.
Попутно получаются другие интересные результаты о ресурсно-ограниченной сложности по Колмогорову.
Доклад будет сделан на основе статьи H. Buhrman, L. Fortnow, "Resource-Bounded Kolmogorov Complexity Revisited", STACS-97.

Семинар 30 ноября 1999 года

Вторник, 30 ноября, комната 106. Начало в 18:00.

30 ноября.
В.Жижкун "Представление булевых функций ациклическими направленными графами"
АБСТРАКТ
Binary Decision Diagrams (BDDs) - способ представления логических функций, позволяющий эффективно реализовать различные операции над ними. В том, что такая проблема достаточно актуальна, можно убедиться, например, построив КНФ отрицания формулы в КНФ. Преимущество BDD в том, что результаты операций над булевыми формулами представляются компактно.
Кроме того, BDD - каноническая форма, поэтому проверка двух функций на эквивалентность заключается в сравнении двух направленых ациклических размеченых графов, а выполнимость формулы - сравнение соответствующего графа с тривиальным.
Существенный недостаток этого способа - необходимость фиксировать порядок переменных. Кроме того, размер графов существенно зависит от выбора такого порядка. Помимо этого, известно, что представление функции умножения двоичных чисел с помощью BDD требует экспоненциального числа узлов при любой перестановке переменных.
Доклад будет сделан на основе статьи Randal E. Bryant "Graph-Based Algorithms for Boolean Function Manipulation".

Семинар 23 ноября 1999 года

Вторник, 23 ноября, комната 106. Начало в 18:00.

23 ноября.
Д.В.Карпов, доклад по статье
D.Achlioptas, M.Molloy "Almost all graphs with 2.522N edges are not 3-colorable". (The Electronic Journal of Combinatorics, 6(1999), #R29)
Abstract. B этой работе доказывается, что для любого с>=2.522, вершины случайного графа с N вершинами и 2.522N ребрами нельзя правильным образом раскрасить в три цвета с вероятностью 1-o(1). Также в этой работе рассматтривается рассматривается аналогичный вопрос для k-раскрашиваемости при k>3, приводятся соответствующие оценки.

Семинар 16 ноября 1999 года

Вторник, 16 ноября, комната 106. Начало в 18:00.

16 ноября.
Б.Ю.Конев. Доклад о патентованном алгоритме Stalmark'а установления тавтологичности пропозициональных формул. Судя по результатам машинных тестов, алгоритм является достаточно эффективным, авторы утверждают, что время его работы зависит не от количества неизвестных, а от "логической структуры формулы". Алгоритм достаточно прост, но никаких оценок для него не известно. Доклад будет сделан на основе статьи John Harrison "Stalmark's Algorithm as a HOL Derived Rule", однако, детали реализации освещаться не будут.

Семинар 2 ноября 1999 года

Вторник, 2 ноября, комната 106. Начало в 18:00.

2 ноября.
В.Жижкун "Разрешимые частные случаи задачи квазиунификации".
АБСТРАКТ
Задача квазиунификации возникает естественным образом в теории логического вывода при при изучении возможности обобщения доказательств (гипотеза Крайзеля). В общей постановке задача оказывается алгоритмически неразрешимой. В докладе будет приведен общий (естественно, неполный) алгоритм ее решения, а также полные алгоритмы для двух частных случаев, имеющих конкретное применение в теории вывода. Эти алгоритмы позволяют получить верхние оценки высоты термов в решении.

Семинар 19 октября 1999 года

Вторник, 19 октября, комната 106. Начало в 18:00.

19 октября.
М.Всемирнов "Арифметика кватернионов и графы Рамануджана"
Графы Рамануджана определяются в терминах спектра матрицы смежности. Такие графы обладают многими замечательными свойствами.
В настоящее время известно несколько принципиально различных явных конструкций графов Рамануджана. Одна из них, принадлежащая Маргулису- Любоцкому- Сарнаку, основанная на арифметических свойствах кватернионов, и будет представлена в докладе.
Конструкция будет описана явно. К сожалению, провести все необходимые доказательства в рамках одной лекции практически невозможно. С другой стороны, чуть менее сложно удается доказать (что и будет сделано), что такие графы имеют большой обхват. (Обхват - длина кратчайшего простого цикла)
Дальнейшие подробности зависят от интереса слушателей к этой тематике.

Семинар 12 октября 1999 года

Вторник, 12 октября, комната 106. Начало в 18:00.

12 октября.
Э.Гирш. Доклад о новых результатах о выполнимости (независимый, но непересекающийся с докладом в понедельник).
Точный круг вопросов будет определен по результатам обсуждения доклада в понедельник, но во всяком случае в доклад войдут результаты, касающиеся "фазового перехода" для выполнимости. Кратко, тематика такова: для 2-выполнимости известно, что если в формуле соотношение кол-ва дизъюнкций и переменных < 1, то формула почти наверняка выполнима, а если > 1, то почти наверняка невыполнима. Уже для 3-выполнимости точная оценка неизвестна, из компьютерных экспериментов предполагается, что граничное соотношение должно быть около 4.25. Будут рассказаны какие-либо из оценок этого соотношения сверху и/или снизу (в преддверии надвигающегося доклада Д.В.Карпова о похожем результате для 3-раскрашиваемости.)

Семинар 7 октября 1999 года

Четверг, 7 октября, комната 106. Начало в 18:00.

7 октября.
Д.В.Карпов "Экстремальные графы без K_{2,n} и без K_{3,3}. Cерии примеров."
Абстракт. Будет построена серия примеров графов без K_{3,3} из работы W.G. Brown. "On graphs that do not contain a Thomsen graph." (Canad. Math. Bull, Vol.9, No.3 (1966), p.281-285). В графах из этой серии количество ребер имеет тот же порядок, что и в доказанной в предыдущем докладе оценке сверху.
Также будут построены две серии примеров графов, не содержащих подграф $ K_{2,n} $ (для фиксированного натурального $ n $), взятые из неопубликованной работы Д.Карпова и С. Берлова "О наибольшем количестве ребер в графе, не содержащем K_{2,n}. Одна серия построена с помощью линейных отображений на проективной плоскости над полем F_p, a другая серия -- на основе двумерного векторного пространства над полем F_{p^\phi(n)}. C помощью этих примеров будет доказано, что при натуральном n, ex(V,K_{2,n+1})= 0.5*n^0.5*V^1.5 + o(V^{4/3}).

Семинар 28 сентября 1999 года

Вторник, 28 сентября, комната 106. Начало в 18:00.

28 сентября.
В.П.Оревков "Обратный метод для скулемовского случая"
АБСТРАКТ
В докладе будет изложен обратный метод поиска вывода для формул в скулемовской нормальной форме (формула находится в скулемовской нормальной форме, если она находится в предваренной форме и в префиксе кванторы существования не следуют за кванторами всеобщности). Будет также доказана разрешимость некоторых классов исчисления предикатов.

Семинар 20 сентября 1999 года

Понедельник, 20 сентября, комната 106. Начало в 18:00.

20 сентября.
Б.Ю.Конев прореферирует статью Владимира Лифшица
``What is the inverse method?''.
Будет рассказано о предложенном С.Ю.Масловым методе автоматического поиска вывода для исчисления предикатов первого порядка. Изложение будет расширено материалом из дополнения А к книге Ч. Чень, Р. Ли ``Математическая логика и автоматическое доказательство теорем'', авторы С.Ю.Маслов и Г.Е.Минц.

Syndicate content