Laboratory of Mathematical Logic at PDMI

Пятница, 13 июля, 203. Начало в 13:30.

Докладчик: Д. Соколов.

Тема: От доказательств к вычислениям.

Abstract

Монотонные Span Programs (mSP) были предложены Карчмером и Вигдерсоном в начале 90-х годов, позднее было
доказано, что они моделируют монотонные булевы формулы. Также известно квазиполиномиальное разделение между
mSP над полем F_2 и монотонными схемами.

Пользуясь недавними теоремами о лифтинге мы покажем, что задача о разделении данных моделей вычислений следует из разделения резолюционной системы доказательств и Nullstellensatz. Мы предъявим экспоненциальное разделение данных систем.