RUS  ENG
Полная версия
СЕМИНАРЫ

Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН
22 ноября 2021 г. 13:00, г. Санкт-Петербург, ПОМИ, комн. 311 (наб. р. Фонтанки, 27). Также будет трансляция в Zoom, см. https://logic.pdmi.ras.ru/GeneralSeminar/index-r.html


Нижние оценки длин доказательств с помощью коммуникационных аргументов

Д. М. Ицыксон

Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук



Аннотация: Рассмотрим такую игру: у каждого из двух участников есть подмножество одного и того же $n$-элементного множества, им требуется узнать, пересекаются ли их множества, передав как можно меньшее количество битов информации. Результат Калянасундарама и Шнитгера 1992 года гласит, что даже, если у участников будет доступ к общему источнику случайности и им требуется узнать верный ответ с вероятностью хотя бы $0.9$, то для этого в худшем случае им придется передать как минимум $Cn$ битов, где $C$ — константа.
В докладе мы увидим, как этот результат может быть использован для доказательства нижних оценок длин вывода в пропозициональных системах доказательств. Сначала мы продемонстрируем этот метод на элементарном примере для одной конкретной системы доказательств (в этой системе невыполнимость пропозициональной формулы показывается рассмотрением случаев значения четности суммы переменных). Затем мы поговорим о том, как этот метод обобщается для многих других систем доказательств.
Для понимания доклада не требуется никаких специальных знаний.


© МИАН, 2024