Том 17, номер 6, 2010 г., Стр. 68-76

УДК 519.714
Рычков К. Л.
Нижняя оценка сложности реализации в классе $\pi$-схем $q$-ичного счётчика кратности $q$

Аннотация:
Рассматривается обобщение понятия параллельно-последовательной контактной схемы ($\pi$-схемы) на случай, когда переменные, приписанные контактам, могут принимать не два, как в булевом случае, а большее число значений. При этом проводимость контакта по-прежнему остаётся двузначной (контакт либо замкнут, либо разомкнут). Получена нижняя оценка сложности таких схем, реализующих $q$-ичный счётчик кратности $q$, т.е. функцию $\varphi_q\colon\{0,1,\dots,q-1\}^n\to\{0,1\}$, которая равна 1, если сумма значений её переменных кратна $q$.
Библиогр. 6.

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

Рычков Константин Леонидович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: rychkov@math.nsc.ru

Статья поступила 26 июня 2010 г.