Laboratory of Mathematical Logic at PDMI

Понедельник, 15 февраля, комната 203. Начало в 13:00.

Докладчик: A. Смаль.

Тема: Эффективное моделирование систем доказательств.

Abstract

Доклад по статье Toniann Pitassi и Rahul Santhanam "Effectively Polynomial Simulations".
Для сравнения двух систем доказательств принято использовать понятие моделируемости (simulation). Авторы статьи предлагают более общее понятие - "эффективное моделирование" (efficient simulation). В статье приводятся аргументы, почему данное понятие более естественно. Пересмотр привычных концепций с точки зрения эффективного моделирования приводит к некоторым неожиданным результатам. Так, к примеру, некоторые пропозициональные системы эффективно моделируют друг друга, в то время как моделирование в классическом смысле отсутствует. Авторы также доказывают, что весьма слабая система G0 для QBF может эффективно моделировать любую систему доказательств для QBF. В заключение доказывается связь между эффективным моделированием, автоматизируемостью и "P vs NP".