DM Seminar

Discrete Mathematics Seminar

Семинар 21 марта 2000 года

Вторник, 21 марта, комната 412. Начало в 15:00.

Докладчик: В. Жижкун.

ДОКАЗАТЕЛЬСТВА КАК ИГРЫ
доклад на основе статьи p.pudlak "proofs as games" (http://www.math.cas.cz/~pudlak/prfgame.ps)
Предлагается интересный способ получения нижней оценки (экспоненциальной) размера вывода pigeon hole principle методом резолюций. Вывод рассматривается как игра двух игроков: prover'а, который пытается получить противоречие из отрицания доказываемой формулы, и его оппонента, который пытается ему в этом помешать. В таких терминах нижняя оценка соответствует оптимальной стратегии оппонента.

Семинар 13 марта 2000 года

Понедельник, 13 марта, комната 203. Начало в 14:30.

Докладчик: Б. Конев.

Доклад будет сделан на основе статьи Atserias, Galesi, Gavald`a
MONOTONE PROOFS OF THE PIGEON HOLE PRINCIPLE
Abstract of this paper: We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We show that the standard encoding of the PHP as a monotone sequent admits quasipolynomial-size proofs in this system. This result is a consequence of deriving the basic properties of certain quasipolynomial-size monotone formulas computing the boolean threshold functions. Since it is known that the shortest proofs of the PHP in systems such as Resolution or Bounded Depth Frege are exponentially long, it follows from our result that these systems are exponentially separated from the monotone Gentzen Calculus. We also consider the monotone sequent (CLIQUE) expressing the clique-coclique principle defined by Bonet, Pitassi and Raz (1997). We show that monotone proofs for this sequent can be easily reduced to monotone proofs of the one-to-one and onto PHP, and so CLIQUE also has quasipolynomial-size monotone proofs. As a consequence, Cutting Planes with polynomially bounded coefficients is also exponentially separated from the monotone Gentzen Calculus. Finally, a simple simulation argument implies that these results extend to the Intuitionistic Gentzen Calculus. Our results partially answer some questions left open by P. Pudl'ak.
Full text: ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2000/TR00-008/index.html

Семинар 22 февраля 2000 года

Вторник, 22 февраля, комната 106. Начало в 17:00.

Докладчик: В. Жижкун.

ВОССТАНОВЛЕНИЕ ДОКАЗАТЕЛЬСТВ ПО СХЕМЕ В СЕКВЕНЦИАЛЬНЫХ ИСЧИСЛЕНИЯХ
Известно, что восстановление доказательства данной секвенции по схеме - алгоритмически неразрешимая задача для исчисления LK^{\Pi\Sigma} (стандартное секвенциальное исчисление в сечениями только по предваренным формулам с "однородным" кванторным префиксом: либо только кванторы всеобщности, либо только существования). Однако оказалось, что если в этом исчислении заменить правила введения квантора на правила введения произвольного числа кванторов, то такая задача становится разрешимой для древовидных доказательств. Результат тем более интересен, так как два упомянутых исчисления эквивалентны с точки зрения выводимости.

Семинар 16 февраля 2000 года

Cреда, 16 февраля, комната 106. Начало в 15:00.

Докладчик: Д. В. Карпов, А. В. Пастор.

БЛОЧНАЯ СТРУКТУРА $ K $-СВЯЗНЫХ ГРАФОВ И УДАЛЕНИЕ ВЕРШИН БЕЗ ПОТЕРИ $ K $-СВЯЗНОСТИ
В докладе будут изложены некоторые результаты относительно возможности удаления из $ k $-связного графа вершин без потери $ k $-связности. Также будет изложена конструкция, обобщающая разбиене связного графа на двусвязные блоки для случая $ k $-связных графов.

Семинар 8 февраля 2000 года

Вторник, 8 февраля, комната 106. Начало в 15:00.

Докладчик: В. П. Оревков.

ПРЯМОЙ И ОБРАТНЫЙ МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ
В докладе будут описаны три варианта прямого (табличного) метода поиска доказательств в исчислении предикатов и построены соответствующие им варианты обратного метода. В частности, метод резолюций будет по этой схеме частным случаем обратного метода.

Семинар 1 февраля 2000 года

Вторник, 1 февраля, комната 106. Начало в 15:00.

Докладчик: М. А. Всемирнов.

ВВЕДЕНИЕ В ТЕОРИЮ КОДОВ (продолжение)
Доклад представляет собой обзор классических результатов в теории кодов. В частности, будет расказано о наиболее известных кодах и об их применении. Доклад основан на 3 главе книги Конвея и Слоана "Упаковки сфер, решетки и группы."

Семинар 18 января 2000 года

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

Докладчик: Г. В. Давыдов, И. М. Давыдова.

"О вычислении формул сечения при поиске вывода в исчислении предикатов"
Правило резолюций в методе резолюций Робинсона и правило Б в обратном методе Маслова являются правилами сечения по контрарной паре в первом случае и по исходной "clause" во втором. Выводом исходной формулы является вывод пустого объекта по этим правилам. В докладе предлагается, наоборот, по исходной формуле строить формулу сечения таким образом, что устранение сечения приводит к реконструкции исходных контрарных пар и исходных "clauses". Построенная формула сечения оказывается исходной для следующего шага. Последовательность формул сечения, оканчивающаяся пропозиционально выводимой формулой, является выводом исходной формулы.

Семинар 10 января 2000 года

Понедельник, 10 января, комната 203. Начало в 14:30.

Докладчик: Б. Ю. Конев.

"Подход Г.Чайтина к колмогоровской сложности"
Этот подход отличается тем, что, в частности, предлагается ограничиться только такими программами универсальной машины Тьюринга, для которых никакой префикс не является программой (self-delimiting programs). Это позволяет ввести вероятность остановки $ \Omega $ (halting probability). Будут рассмотрены свойства введенных понятий, а также следствия для алгоритмической теории информации.

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

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

28 декабря.
М.А.Всемирнов "Реберные раскраски графов, Nullstellensatz и вычисление определителей".
Предлагается новый критерий существования реберных k-раскрасок графов, формулируемый в терминах обращения в 0 определителей специального вида. Тематически этот доклад связан с предыдущим докладом Д.В.Карпова и Ю.В.Матиясевича, однако изложение носит независимый характер.

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

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

21 декабря.
Д.В.Карпов, Ю.В.Матиясевич
В первой части Д.В.Карпов изложит по статье N. Alon "Combinatorial Nullstelensatz" (Combinatorics Probability and Computing 1999, N8, p7-29) технику сведения комбинаторных проблем (в частности, связанных с раскрасками графов) к вопросам о нулях многочленов.
Во второй части семинара Ю.В.Матиясевич изложит результаты о связи существования правильной раскраски ребер триангуляции сферы и невырожденности специального полинома, соответствующего этому графу. (См. Homepage Ю.В.Матиясевича http://logic.pdmi.ras.ru/~yumat/ и статью Ю.В.Матиясевича "Один критерий раскрашиваемости вершин графа, формулируемый в терминах ориентации ребер" (Дискретный анализ, N26(1974) )

Syndicate content