Минимальные контактные схемы для характеристических функций сфер

В работе исследуется сложность реализации контактными схемами характеристических функций сфер. Под характеристической функцией сферы с центром в вершине $\tilde\sigma=(\sigma_1,\ldots,\sigma_n)$, $\sigma_1,\ldots,\sigma_n\in\{0,1\}$, подразумевается булева функция $\varphi^{(n)}_{\tilde\sigma}(x_1,\ldots,x_n)$, обращающаяся в единицу на всех тех и только тех наборах значений, каждый из которых отличается от набора $\tilde\sigma$ ровно в одном разряде. Устанавливается, что для реализации $\varphi^{(n)}_{\tilde\sigma}(\tilde x)$ контактной схемой необходимо и достаточно $3n-2$ контактов.