Пятница 13.07. Д. Соколов: "От доказательств к вычислениям"

Пятница 13.07. Д. Соколов: "От доказательств к вычислениям"

Date:

Friday, July 13, 2018 - 13:30

Abstract:

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

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