Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 18/2008

СХЕМНАЯ СЛОЖНОСТЬ MOD-ФУНКЦИЙ

АННОТАЦИЯ:
В 1977-м году Стокмайер показал, что любая схема над полным бинарным базисом
  для некоторого класса симметрических функций, содержащего все функции
  MOD_m^n ($m \ge 3$),
  содержит хотя бы 2.5n-c гейтов.
  Он также представил оптимальную схему для MOD_4^n.
  В данной работе мы приводим модифицированное доказательство
Стокмайера, дающее нижную оценку
  $2.5n-c$ для другого класса, содержащего не только симметрические
функции. Этот класс, в частности,
  содержит функцию MOD_3^n. Мы также даём очень простое
доказательство нижней оценки
  7n/3-c для класса функций, задаваемых полиномами Жегалкина высокой степени.
  Основной идеей является комбинированная мера сложности,
присваивающая разные веса гейтам
  разных типов. В конце работы мы также приводим схему размера 3n для функции
  MOD_3^n и описываем способ, с помощью которого она была найдена.

Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev

CIRCUIT COMPLEXITY OF MOD-FUNCTIONS


  In 1977, Stockemyer proved that any circuit over the full binary basis for a
  certain class of symmetric Boolean functions including all
$\mathrm{MOD}_m^n$ functions ($m \ge 3$)
  contains at least $2.5n-c$ gates.
  He also presented an optimal circuit for $\mathrm{MOD}_4^n$.
  In this paper we give a modification of Stockmeyer's proof yielding
a $2.5n-c$ lower bound for
  a different class of functions containing not only symmetric
functions. This class, in particular,
  contains the function $\mathrm{MOD}_3^n$. We also give a very simple proof of
  a $7n/3$ lower bound for a class of functions represented by high
degree polynomials over $\mygftwo$.
  The key idea of this proof is a combined complexity measure which
assigns different weights
  to gates of different types.
  In the end of the paper we present
  a circuit of size $3n$ for the function $\mathrm{MOD}_3^n$ and
briefly describe the way it was found.