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

ПРЕПРИНТ 18/2008


А. А. Кожевников, А. С. Куликов, Г. Н. Ярославцев

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

С.-Петербургское отделение Математического института им. В.А.Стеклова РАН, Фонтанка 27, 191023, С.-Петербург, Россия
kulikov@logic.pdmi.ras.ru
Академический физико-технологический университет Российской академии наук
http://logic.pdmi.ras.ru/~grigory
This preprint was accepted November 2008
АННОТАЦИЯ:
В 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.

[Full text: Preprint in Russian (.ps.gz) Preprint in English (.ps.gz)]
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg