Пороговые элементы на множестве $\{1,2\}$ и пороговые схемы

Полиномиальным пороговым элементом для булевой функции $f\colon\{a,b\}^n\to\{a,b\}$ называется целочисленный многочлен $p$ от $n$ переменных, такой что для всякого $x$ из $\{a,b\}^n$ верно $p(x)>0$ тогда и только тогда, когда $f(x)=b$. Обычно, когда говорят о вычислении булевых функций пороговыми элементами, булевы функции рассматриваются как функции на переменных $\{0,1\}$ или $\{-1,1\}$. В рамках доклада мы будем рассматривать реализацию пороговыми элементами булевых функций с произвольными значениями переменных $\{a,b\}$. Типичным случаем являются значения переменных $\{1,2\}$. Основной мерой сложности пороговых элементов будет число мономов в них, второй мерой сложности будет степень пороговых элементов. Оказывается, что эта модель вычислений сильнее чем аналогичные модели над переменными $\{0,1\}$ и $\{-1,1\}$. Кроме того, оказывается, что эта модель тесно связана с пороговыми схемами глубины $2$. Эта связь является основной мотивацией для изучения пороговых элементов над переменными $\{1,2\}$.
В докладе будет рассказано о структурных результатах о пороговых элементах над переменными $\{1,2\}$ и о связи этих пороговых элементов с пороговыми схемами.
Доклад основан на совместной работе с Кристоффером Хансеном. Ссылка на работу: http://eccc.hpi-web.de/report/2013/021/