Схемы для функции голосования и других пороговых функций. Александр Козачинский (17.03.2021)

По совместной работе с В. Подольским (Computational Complexity Conference, 2020).

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

Этот вопрос был чрезвычайно актуален после того, как Разборов (1985) показал, что некоторая монотонная булева функция из класса NP не может быть вычислена схемой полиномиального размера в монотонном базисе. Если бы наличие схемы полиномиального размера в стандартном полном базисе влекло наличие схемы полиномиального размера в монотонном базисе (для монотонных функций), то из результата Разборова вытекало бы, что P не равно NP! Однако Разборов же (позже в 1985) доказал, что одно не всегда влечет другое, так что доказать неравенство P и NP таким способом не получится.

Вместо монотонных функций мы рассмотрели аналогичный вопрос для класса самодвойственных функций (т.е. функций, принимающих противоположные значения в противоположных точках булева куба), и там ситуация оказалась противоположной. Стандартный базис для этого класса состоит из функции голосования от 3 переменных и отрицания. Мы показали, что если самодвойственная функция имеет схему полиномиального размера в стандартном полном базисе, то эта функция имеет и схему полиномиального размера в стандартном самодвойственном базисе. Доказан также аналогичный результат о переходе от схем в монотонном базисе к схемам в базисе, состоящим из одной лишь функции голосования от 3 переменных (для функций, являющимися одновременно монотонными и самодвойственными). Отметим, что эти результаты верны не только для размера, но и для глубины схем.

Мы применяем наш результат к функции голосования от n переменных при нечетном n (это функция монотонна и самодвойственна). Для этой функции давно известна явная конструкция схемы логарифмической по n глубины в монотонном базисе. Благодаря нашему результату отсюда извлекается явная схема логарифмической по n глубины, состоящая только из функций голосования от 3 переменных. У этого результата имеются следствия в области протоколов конфиденциального вычисления (Кохен и др. 2013). Для схем, состоящих только из функций голосования от 3 переменных, ранее была известна лишь неявная конструкция (Вэлиент, 1984).

Помимо функции голосования, мы изучаем также другие пороговые функции, получая для них усиления известных результатов. Здесь вместо теорем о переходе от одних схем к другим нам потребовались другие технические инструменты, а именно коммуникационная сложность. Мы получили новый результат о переходе от коммуникационных протоколов к булевым схемам, обобщающий известный результат Карчмера и Вигдерсона (1991).

============================================

Научно-исследовательский семинар
по математической логике
под руководством
академика РАН Л. Д. Беклемишева
и академика РАН А. Л. Семёнова
(по средам в 18:30)

Веб-страница семинара (и слайды):