Том 25, номер 1, 2018 г., Стр. 120–141

УДК 519.7
Сергеев И. С.
Вентильные схемы ограниченной глубины

Аннотация:
Получены асимптотически точные оценки сложности вычисления классов $(m, n)$-матриц с коэффициентами из множества ${0, 1, \dots , q - 1}$ вентильными схемами ограниченной глубины $d$ при некоторых соотношениях между $m$, $n$ и $q$. В наиболее важном случае $q = 2$ показано, что асимптотика сложности класса булевых $(m, n)$-матриц log $n = o(m)$, log $m = o(n)$, достигается на схемах глубины 3.
Ил. 1, библиогр. 11.

Ключевые слова: вентильные схемы, сложность, глубина.

DOI: 10.17377/daio.2018.25.577

Сергеев Игорь Сергеевич ¹
1. ФГУП «НИИ ”Квант“»,
4-й Лихачёвский пер., 15, 125438 Москва, Россия
е-mail: isserg@gmail.com

Статья поступила 19 апреля 2017 г.
Исправленный вариант — 4 сентября 2017 г.

Литература

[1] Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности. Вып. 52. Новосибирск, Ин-т математики СО РАН, 1992. C. 22–40.

[2] Гашков С. Б., Сергеев И. С. О применении метода аддитивных цепочек к инвертированию в конечных полях // Дискрет. математика. 2006. Т. 18, вып. 4. C. 56–72.

[3] Кочергин В. В. О сложности вычисления систем одночленов с ограничениями на степени переменных // Дискрет. математика. 1998. Т. 10, вып. 3. C. 27–34.

[4] Кочергин В. В. Теория вентильных схем (современное состояние) // Дискретная математика и ее приложения. Вып. 7. М.: Изд-во ИПМ РАН, 2013. C. 23–40.

[5] Лупанов О. Б. О вентильных и контактно-вентильных схемах // Докл. АН СССР. 1956. Т. 111, № 6. C. 1171–1174.

[6] Нечипорук Э. И. О вентильных схемах // Докл. АН СССР. 1963. Т. 148, № 1. C. 50–53.

[7] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. C. 5–102.

[8] Brauer A. On addition chains // Bull. Amer. Math. Soc. 1939. Vol. 45. P. 736–739.

[9] Jukna S., Sergeev I. Complexity of linear Boolean operators // Found. Trends Theor. Comput. Sci. 2013. Vol. 9, No. 1. P. 1–123.

[10] Pippenger N. The minimum number of edges in graphs with prescribed paths // Math. Syst. Theory. 1979. Vol. 12. P. 325–346.

[11] Pippenger N. On the evaluation of powers and monomials // SIAM J. Comput. 1980. Vol. 9, No. 2. P. 230–250.