О проверке выполнимости алгебраических формул над полем из двух элементов

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